# 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:

[
[3],
[1],
[2],
[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 [1] now
Combine them, now we have [ [ ], [1] ] as all possible subset

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

Next considering 3, if not use it, we still have [ [ ], [1], [2], [1,2] ], if use 3, just add 3 to each previous subset, we have [ [3], [1,3], [2,3], [1,2,3] ]
Combine them, now we have [ [ ], [1], [2], [1,2], [3], [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));