# 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-%28Subsets-Permutations-Combination-Sum-Palindrome-Partitioning\)\\)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/backtracking/subsets.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.