Subsets

Given a set of distinct integers,nums, return all possible subsets (the power set).

Note:The solution set must not contain duplicate subsets.

Example:

Input:
nums = [1,2,3]

Output:

[
,
,
,
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Analysis

Iterative

https://leetcode.com/problems/subsets/discuss/122645/3ms-easiest-solution-no-backtracking-no-bit-manipulation-no-dfs-no-bullshit

While iterating through all numbers, for each new number, we can either pick it or not pick it

1, if pick, just add current number to every existing subset.

2, if not pick, just leave all existing subsets as they are.

We just combine both into our result.

For example, {1,2,3} intially we have an emtpy set as result [ [ ] ]
Considering 1, if not use it, still [ ], if use 1, add it to [ ], so we have  now
Combine them, now we have [ [ ],  ] as all possible subset

Next considering 2, if not use it, we still have [ [ ],  ], if use 2, just add 2 to each previous subset, we have , [1,2]
Combine them, now we have [ [ ], , , [1,2] ]

Next considering 3, if not use it, we still have [ [ ], , , [1,2] ], if use 3, just add 3 to each previous subset, we have [ , [1,3], [2,3], [1,2,3] ]
Combine them, now we have [ [ ], , , [1,2], , [1,3], [2,3], [1,2,3] ]

Bit Manipulation

https://leetcode.com/problems/subsets/discuss/122645/3ms-easiest-solution-no-backtracking-no-bit-manipulation-no-dfs-no-bullshit

Solution

Backtracking

class Solution {
public List<List<Integer>> subsets(int[] ns) {
List<List<Integer>> acc = new ArrayList<>();

recur(acc, ns, new ArrayDeque<>(), 0);
return acc;
}

private void recur(List<List<Integer>> acc, int [] ns, Deque<Integer> path, int start){
if(ns.length == start){
return;
}

// take ns[start]
path.push(ns[start]);
recur(acc, ns, path, start + 1);

// dont take ns[start]
path.pop();
recur(acc, ns, path, start + 1);
}
}

Another Backtracking

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
for(int i = start; i < nums.length; i++){
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

Iteration

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
for(int n : nums){
int size = result.size();
for(int i=0; i<size; i++){
List<Integer> subset = new ArrayList<>(result.get(i));
}
}
return result;
}

Bit Manipulation

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
for(int n : nums){
int size = result.size();
for(int i=0; i<size; i++){
List<Integer> subset = new ArrayList<>(result.get(i));