# Question

Formatted question description: https://leetcode.ca/all/78.html

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]


Example 2:

Input: nums = [0]
Output: [[],[0]]


Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

# Algorithm

For the example [1,2,3] given in the title,

• it is an empty set at the beginning,
• then we have to deal with 1, add 1 to the empty set, which is [1], and now we have two selves [] And [1],
• let’s deal with 2, we add 2 to each of the previous subsets, and we can get [2], [1, 2], then all the subsets are now [], [1], [2], [1, 2],
• in the same way, we can get [3], [1, 3], [2, 3], [1, 2, 3], plus all of previous the subsets
[]
[1]
[2]
[1 2]
[3]
[1 3]
[2 3]
[1 2 3]


# Code

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets {

public class Solution {
public List<List<Integer>> subsets(int[] nums) {

List<List<Integer>> list = new ArrayList<>();
if (nums == null || nums.length == 0) {
return list;
}

Arrays.sort(nums); // requirement: non-descending order

// prepare, add empty one to start looping then.
// @note: I forgot empty
ArrayList<Integer> empty = new ArrayList<>();

for (int i = 0; i < nums.length; i++) {
int numToAdd = nums[i];
List<List<Integer>> newlyAddedList = new ArrayList<>(list);

for (List<Integer> each : list) {
ArrayList<Integer> newOne = new ArrayList<Integer>(each); // deep copy

}

}

return list;
}
}

class Solution_dfs {

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
getAns(nums, 0, new ArrayList<>(), ans);
return ans;
}

private void getAns(int[] nums, int start, ArrayList<Integer> temp, List<List<Integer>> ans) {
ans.add(new ArrayList<>(temp)); // @note: deep copy
for (int i = start; i < nums.length; i++) {
getAns(nums, i + 1, temp, ans);
temp.remove(temp.size() - 1);
}
}
}

}

############

class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private int[] nums;

public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0, new ArrayList<>());
return ans;
}

private void dfs(int u, List<Integer> t) {
if (u == nums.length) {
return;
}
dfs(u + 1, t);
dfs(u + 1, t);
t.remove(t.size() - 1);
}
}

• // OJ: https://leetcode.com/problems/subsets/
// Time: O(N * 2^N)
// Space: O(N)
class Solution {
public:
vector<vector<int>> subsets(vector<int>& A) {
vector<vector<int>> ans;
vector<int> tmp;
function<void(int)> dfs = [&](int i) {
if (i == A.size()) {
ans.push_back(tmp);
return;
}
tmp.push_back(A[i]);
dfs(i + 1); // Pick A[i]
tmp.pop_back();
dfs(i + 1); // Skip A[i]
};
dfs(0);
return ans;
}
};

• from typing import List

class Solution: # bfs
def subsets(self, nums: List[int]) -> List[List[int]]:
if not nums:
return [[]]

nums.sort() # sort() not necessary if no duplicates
result = [[]]

for num in nums:
result += [subset + [num] for subset in result]

return result

class Solution: # dfs
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(u, t):
ans.append(t[:]) # or, t.copy()
for i in range(u, len(nums)):
t.append(nums[i])
dfs(i + 1, t)
t.pop()

ans = []
nums.sort() # sort() not necessary if no duplicates
dfs(0, [])
return ans

class Solution: # dfs, just pass down the final path
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(nums, index, path, ans):
ans.append(path)
[dfs(nums, i + 1, path + [nums[i]], ans) for i in range(index, len(nums))]

ans = []
dfs(nums, 0, [], ans)
return ans

class Solution: # dfs, but running slower, since need to reference from parent method for 'nums' and 'ans'
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(index, path):
ans.append(path)
[dfs(i + 1, path + [nums[i]]) for i in range(index, len(nums))]

ans = []
dfs(0, [])
return ans


• func subsets(nums []int) [][]int {
var ans [][]int
var dfs func(u int, t []int)
dfs = func(u int, t []int) {
if u == len(nums) {
ans = append(ans, append([]int(nil), t...))
return
}
dfs(u+1, t)
t = append(t, nums[u])
dfs(u+1, t)
t = t[:len(t)-1]
}
var t []int
dfs(0, t)
return ans
}

• function subsets(nums: number[]): number[][] {
const n = nums.length;
const t: number[] = [];
const res: number[][] = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...t]);
return;
}
dfs(i + 1);
t.push(nums[i]);
dfs(i + 1);
t.pop();
};
dfs(0);
return res;
}


• impl Solution {
fn dfs(i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
if i == nums.len() {
res.push(t.clone());
return;
}
Self::dfs(i + 1, t, res, nums);
t.push(nums[i]);
Self::dfs(i + 1, t, res, nums);
t.pop();
}

pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = Vec::new();
Self::dfs(0, &mut Vec::new(), &mut res, &nums);
res
}
}