# 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

### Backtracking

典型的backtracking问题，可以用比较通用的模板来解决。

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

```java
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){
            acc.add(new ArrayList<>(path));
            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

```java
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){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}
```

Iteration

```java
public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(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));
                subset.add(n);
                result.add(subset);
            }
        }
        return result;
    }
```

Bit Manipulation

```java
public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(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));
                subset.add(n);
                result.add(subset);
            }
        }
        return result;
    }
```

## Reference

[https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning\\](https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-\(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning\)/)