78. All subsets

78_solution1_branching.c

#include <stdlib.h>
#include <string.h>

static void backtrack(int *nums, int n, int idx, int *cur, int curSize,
                      int **result, int *returnSize, int *colSizes) {
  if (idx == n) {
    result[*returnSize] = malloc(curSize * sizeof(int));
    memcpy(result[*returnSize], cur, curSize * sizeof(int));
    colSizes[(*returnSize)++] = curSize;
    return;
  }
  // include nums[idx]
  cur[curSize] = nums[idx];
  backtrack(nums, n, idx + 1, cur, curSize + 1, result, returnSize, colSizes);

  // skip nums[idx] (undo is implicit: curSize is unchanged)
  backtrack(nums, n, idx + 1, cur, curSize, result, returnSize, colSizes);
}

int **subsets(int *nums, int numsSize, int *returnSize,
              int **returnColumnSizes) {
  int total = 1 << numsSize;
  int **result = malloc(total * sizeof(int *));
  *returnColumnSizes = malloc(total * sizeof(int));
  *returnSize = 0;
  int cur[numsSize > 0 ? numsSize : 1];
  backtrack(nums, numsSize, 0, cur, 0, result, returnSize, *returnColumnSizes);
  return result;
}

78_solution2_loop.c

#include <stdlib.h>
#include <string.h>

static void backtrack(int *nums, int n, int start, int *cur, int curSize,
                      int **result, int *returnSize, int *colSizes) {
  // every path is a valid subset
  result[*returnSize] = malloc(curSize * sizeof(int));
  memcpy(result[*returnSize], cur, curSize * sizeof(int));
  colSizes[(*returnSize)++] = curSize;

  for (int i = start; i < n; i++) {
    cur[curSize] = nums[i];
    backtrack(nums, n, i + 1, cur, curSize + 1, result, returnSize, colSizes);
  }
}

int **subsets(int *nums, int numsSize, int *returnSize,
              int **returnColumnSizes) {
  int total = 1 << numsSize;
  int **result = malloc(total * sizeof(int *));
  *returnColumnSizes = malloc(total * sizeof(int));
  *returnSize = 0;
  int cur[numsSize > 0 ? numsSize : 1];
  backtrack(nums, numsSize, 0, cur, 0, result, returnSize, *returnColumnSizes);
  return result;
}

78_solution1_branching.cpp

#include <vector>

using namespace std;

class Solution {
public:
  vector<vector<int>> subsets(vector<int> &nums) {
    vector<vector<int>> result;
    vector<int> cur;
    backtrack(nums, 0, cur, result);
    return result;
  }

  void backtrack(vector<int> &nums, int idx, vector<int> &cur,
                 vector<vector<int>> &result) {
    if (idx == nums.size()) {
      result.push_back(cur);
      return;
    }
    // include nums[idx]
    cur.push_back(nums[idx]);
    backtrack(nums, idx + 1, cur, result);
    cur.pop_back(); // undo

    // skip nums[idx]
    backtrack(nums, idx + 1, cur, result);
  }
};

78_solution2_loop.cpp

#include <vector>

using namespace std;

class Solution {
public:
  vector<vector<int>> subsets(vector<int> &nums) {
    vector<vector<int>> result;
    vector<int> cur;
    backtrack(nums, 0, cur, result);
    return result;
  }

  void backtrack(vector<int> &nums, int start, vector<int> &cur,
                 vector<vector<int>> &result) {
    result.push_back(cur); // every path is a valid subset

    for (int i = start; i < nums.size(); i++) {
      cur.push_back(nums[i]);
      backtrack(nums, i + 1, cur, result);
      cur.pop_back(); // undo
    }
  }
};

78_solution1_branching.go

package backtracking

func subsets(nums []int) [][]int {
    var result [][]int
    var cur []int

    var backtrack func(idx int)
    backtrack = func(idx int) {
        if idx == len(nums) {
            result = append(result, append([]int(nil), cur...))
            return
        }
        // include nums[idx]
        cur = append(cur, nums[idx])
        backtrack(idx + 1)
        cur = cur[:len(cur)-1] // undo

        // skip nums[idx]
        backtrack(idx + 1)
    }

    backtrack(0)
    return result
}

78_solution2_loop.go

package backtracking

func subsets(nums []int) [][]int {
    var result [][]int
    var cur []int

    var backtrack func(start int)
    backtrack = func(start int) {
        result = append(result, append([]int(nil), cur...)) // every path is a valid subset

        for i := start; i < len(nums); i++ {
            cur = append(cur, nums[i])
            backtrack(i + 1)
            cur = cur[:len(cur)-1] // undo
        }
    }

    backtrack(0)
    return result
}

78_solution1_branching.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int idx, List<Integer> cur, List<List<Integer>> result) {
        if (idx == nums.length) {
            result.add(new ArrayList<>(cur));
            return;
        }
        // include nums[idx]
        cur.add(nums[idx]);
        backtrack(nums, idx + 1, cur, result);
        cur.remove(cur.size() - 1); // undo

        // skip nums[idx]
        backtrack(nums, idx + 1, cur, result);
    }
}

78_solution2_loop.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> cur, List<List<Integer>> result) {
        result.add(new ArrayList<>(cur)); // every path is a valid subset

        for (int i = start; i < nums.length; i++) {
            cur.add(nums[i]);
            backtrack(nums, i + 1, cur, result);
            cur.remove(cur.size() - 1); // undo
        }
    }
}

78_solution1_branching.js

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const result = [];
  const cur = [];

  const backtrack = (idx) => {
    if (idx === nums.length) {
      result.push([...cur]);
      return;
    }
    // include nums[idx]
    cur.push(nums[idx]);
    backtrack(idx + 1);
    cur.pop(); // undo

    // skip nums[idx]
    backtrack(idx + 1);
  };

  backtrack(0);
  return result;
};

78_solution2_loop.js

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const result = [];
  const cur = [];

  const backtrack = (start) => {
    result.push([...cur]); // every path is a valid subset

    for (let i = start; i < nums.length; i++) {
      cur.push(nums[i]);
      backtrack(i + 1);
      cur.pop(); // undo
    }
  };

  backtrack(0);
  return result;
};

78_solution1_branching.py

from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        cur: List[int] = []

        def backtrack(idx: int) -> None:
            if idx == len(nums):
                result.append(cur[:])
                return
            # include nums[idx]
            cur.append(nums[idx])
            backtrack(idx + 1)
            cur.pop()  # undo

            # skip nums[idx]
            backtrack(idx + 1)

        backtrack(0)
        return result

78_solution2_loop.py

from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        cur: List[int] = []

        def backtrack(start: int) -> None:
            result.append(cur[:])  # every path is a valid subset

            for i in range(start, len(nums)):
                cur.append(nums[i])
                backtrack(i + 1)
                cur.pop()  # undo

        backtrack(0)
        return result

78_solution1_branching.rs

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::with_capacity(1 << nums.len());
        let mut cur = Vec::with_capacity(nums.len());
        Self::backtrack(&nums, 0, &mut cur, &mut result);
        result
    }

    fn backtrack(nums: &[i32], idx: usize, cur: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if idx == nums.len() {
            result.push(cur.clone());
            return;
        }
        // include nums[idx]
        cur.push(nums[idx]);
        Self::backtrack(nums, idx + 1, cur, result);
        cur.pop(); // undo

        // skip nums[idx]
        Self::backtrack(nums, idx + 1, cur, result);
    }
}

78_solution2_loop.rs

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::with_capacity(1 << nums.len());
        let mut cur = Vec::with_capacity(nums.len());
        Self::backtrack(&nums, 0, &mut cur, &mut result);
        result
    }

    fn backtrack(nums: &[i32], start: usize, cur: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        result.push(cur.clone()); // every path is a valid subset

        for i in start..nums.len() {
            cur.push(nums[i]);
            Self::backtrack(nums, i + 1, cur, result);
            cur.pop(); // undo
        }
    }
}