LeetCode 78 - Subsets


https://leetcode.com/problems/subsets/
LeetCode 46 - Permutations
LeetCode 47 - Permutations II
Given a set of distinct integers, S, return all possible subsets.Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example, If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2],[] ]
For example, given S = [1,2,3], the method returns:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

X. BFS - Iterative Version

 Given a set S of n distinct integers, there is a relation between Sn and Sn-1. The subset of Sn-1 is the union of {subset of Sn-1} and {each element in Sn-1 + one more element}. Therefore, a Java solution can be quickly formalized.
https://leetcode.com/problems/subsets/discuss/27278/C%2B%2B-RecursiveIterativeBit-Manipulation
Using [1, 2, 3] as an example, the iterative process is like:
  1. Initially: [[]]
  2. Adding the first number to all the existing subsets: [[], [1]];
  3. Adding the second number to all the existing subsets: [[], [1], [2], [1, 2]];
  4. Adding the third number to all the existing subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
 if (S == null)
  return null;
 Arrays.sort(S); 
 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 
 for (int i = 0; i < S.length; i++) {
  ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
 
  //get sets that are already in result
  temp.addAll(result);
  //add S[i] to existing sets
  for (ArrayList<Integer> a : temp) {
   a.add(S[i]);
  }
  //add S[i] only as a set
  temp.add(new ArrayList<Integer>(single));
  result.addAll(temp);
 } 
 //add empty set
 result.add(new ArrayList<Integer>());
 return result;
}

Code from http://www.cnblogs.com/TenosDoIt/p/3451902.html
从上面的二叉树可以观察到，当前层的集合 = 上一层的集合 + 上一层的集合加入当前层处理的元素得到的所有集合（其中树根是空集），因此可以从第二层开始（第一层是空集合）迭代地求最后一层的所有集合（即叶子节点

https://leetcode.com/problems/subsets/discuss/27294/simple-iteration-no-recursion-no-twiddling-explanation
public List<List<Integer>> subsets(int[] nums) {
    Arrays.sort(nums); // make sure subsets are ordered
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>()); // start with empty set
    for (int i = 0; i < nums.length; ++i) {
        for (int j = 0, size = result.size(); j < size; ++j) { // remember
            List<Integer> subset = new ArrayList<>(result.get(j)); // copy a new one
            subset.add(nums[i]); // expand
            result.add(subset); // collect
        }
    }
    return result;
}
It is also necessary to order the input to satisfy the requirement:
  • Elements in a subset must be in non-descending order.
Because i is increasing it means that whatever we take from nums will also be in increasing order.
The other requirement:
  • The solution set must not contain duplicate subsets.
is automatically guaranteed by the input specification and the algorithm walking indices straight and once:
Given a set of distinct integers, nums, return all possible subsets. [emphasis mine]
https://discuss.leetcode.com/topic/30867/simple-iteration-no-recursion-no-twiddling-explanation/2
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<Integer>());
        
        Arrays.sort(S);
        for(int i : S) {
            List<List<Integer>> tmp = new ArrayList<>();
            for(List<Integer> sub : res) {
                List<Integer> a = new ArrayList<>(sub);
                a.add(i);
                tmp.add(a);
            }
            res.addAll(tmp);
        }
        return res;
    }

https://leetcode.com/discuss/23159/not-sure-if-this-is-the-best-solution-using-java
public List<List<Integer>> subsets(int[] S) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    res.add(new ArrayList<Integer>());
    Arrays.sort(S);
    for(int i = S.length - 1; i >= 0; i--){
        int size = res.size() - 1;
        for(int j = size; j >= 0; j--){
            List<Integer> newList1 = new ArrayList<>();
            newList1.add(S[i]);
            newList1.addAll(res.get(j));
            res.add(newList1);
        }
    }
    return res;
}
http://blog.welkinlan.com/2015/07/17/subsets-i-subsets-ii-leetcode-java/

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        result.add(new ArrayList<Integer>());
        for (int n : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                List<Integer> l = new ArrayList<Integer>(result.get(i));
                l.add(n);
                result.add(l);
            }
        }
        return result;
    }

X. DFS
https://leetcode.com/problems/subsets/discuss/27332/Java-subsets-solution
public List<List<Integer>> subsets(int[] S) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(S.length == 0){ return result; } Arrays.sort(S); dfs(S, 0, new ArrayList<Integer>(), result); return result; } public void dfs(int[] s, int index, List<Integer> path, List<List<Integer>> result){ result.add(new ArrayList<Integer>(path)); for(int i = index; i < s.length; i++){ path.add(s[i]); dfs(s, i+1, path, result); path.remove(path.size()-1); } }
Same code without needless sorting and empty input check:
class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        dfs(S, 0, new ArrayList<Integer>(), result);
        return result;
    }

    public void dfs(int[] s, int index, List<Integer> path, List<List<Integer>> result){
        result.add(new ArrayList<Integer>(path));

        for(int i = index; i < s.length; i++){
            path.add(s[i]);
            dfs(s, i+1, path, result);
            path.remove(path.size()-1);
        }
    }
}
http://bangbingsyb.blogspot.com/2014/11/leetcode-subsets-i-ii.html
方法2：添加数字构建subset
起始subset集为：[]
添加S0后为：[], [S0]
添加S1后为：[], [S0], [S1], [S0, S1]
添加S2后为：[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]
红色subset为每次新增的。显然规律为添加Si后，新增的subset为克隆现有的所有subset，并在它们后面都加上Si。
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(), S.end());
        for(int i=0; i<S.size(); i++) {
            int n = allSets.size();
            for(int j=0; j<n; j++) {
                sol = allSets[j];
                sol.push_back(S[i]);
                allSets.push_back(sol);
            }
        }
        return allSets;
    }
http://blog.csdn.net/linhuanmars/article/details/24286377
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
     ArrayList<ArrayList<Integer>> res = new  ArrayList<ArrayList<Integer>>();
     res.add(new ArrayList<Integer>());
     if(S == null || S.length == 0)
        return res;
    Arrays.sort(S);
    for(int i=0;i<S.length;i++)
    {
        int size = res.size();
        for(int j=0;j<size;j++)
        {
            ArrayList<Integer> item = new ArrayList<Integer>(res.get(j));
            item.add(S[i]);
            res.add(item);
        }
    }
    return res;
}
https://leetcode.com/discuss/72498/simple-iteration-no-recursion-no-twiddling-explanation
public List<List<Integer>> subsets(int[] nums) {
    Arrays.sort(nums); // make sure subsets are ordered
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>()); // start with empty set
    for (int i = 0; i < nums.length; ++i) {
        for (int j = 0, size = result.size(); j < size; ++j) { // remember
            List<Integer> subset = new ArrayList<>(result.get(j)); // copy a new one
            subset.add(nums[i]); // expand
            result.add(subset); // collect
        }
    }
    return result;
}
My idea was to start out with an empty subset and either take or don't take the next element in the input array. Here's how it goes down for input [1,2,3]:
start with
[] // empty set is always a subset
then either take or not take the next element (1), this doubles the result size:
[]   // not take 1
[1] //      take 1 + new
then take or not take the next element: 2
[]    // not take 1, not take 2
[2]   // not take 1,     take 2 + new
[1]   //     take 1, not take 2
[1,2] //     take 1,     take 2 + new
and finally take or not take 3.
[]      // not take 1, not take 2, not take 3
[3]     // not take 1, not take 2,     take 3 + new
[2]     // not take 1,     take 2, not take 3
[2,3]   // not take 1,     take 2,     take 3 + new
[1]     //     take 1, not take 2, not take 3
[1,3]   //     take 1, not take 2,     take 3 + new
[1,2]   //     take 1,     take 2, not take 3
[1,2,3] //     take 1,     take 2,     take 3 + new
And we're done, we have all 2^3 = 8 subsets generated.
It is possible to generate these with a simple loop, there's only one trick here, the variable size. It's usually a good practice to cache method call results, but now it is cached for a different reason: because it changes in every iteration. If we don't want to end up with an infinite loop, we have to remember how many results were available in the previous iteration, which is exactly the size() of the result at the beginning of the current iteration.
public List<List<Integer>> subsets(int[] nums) {
    Arrays.sort(nums); // make sure subsets are ordered
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>()); // start with empty set
    for (int i = 0; i < nums.length; ++i) {
        for (int j = 0, size = result.size(); j < size; ++j) { // remember
            List<Integer> subset = new ArrayList<>(result.get(j)); // copy a new one
            subset.add(nums[i]); // expand
            result.add(subset); // collect
        }
    }
    return result;
}
It is also necessary to order the input to satisfy the requirement:
  • Elements in a subset must be in non-descending order.
Because i is increasing it means that whatever we take from nums will also be in increasing order.
The other requirement:
  • The solution set must not contain duplicate subsets.
is automatically guaranteed by the input specification and the algorithm walking indices straight and once:
Given a set of distinct integers, nums, return all possible subsets. [emphasis mine]
result.size() changes inside that loop, that's why we need to "remember" it (see comment). Essentiallyresult is the source and target of that inner loop, so we only need to process the part of it that was available at the beginning of each outer loop iteration.
To crossreference the example see the lines that have "+ new" after them, those are the ones that are generated from at "collect" in code, so the result is partitioned into [old values, new values] at the end of the inner loop and both partitions have equal length (size).
A similar description is there in the paragraph just above the code.
https://leetcode.com/discuss/64607/havent-see-dp-solution-here-it-is
1 Start from only 1 dig in the list, then result is obvious, [[],[nums[0]]]
2 Than for each new dig, the result is the previous list + previous list append the new dig, it's easy to understand, since once the new dig come in, there is 2 options, with it or with out it. without it, is the previous result, with it, it to add this dig in each array of the previuos result
def subnets(nums): nums.sort() dp={} dp[0]=[[],[nums[0]] ] for i in range(1,len(nums)): dp[i]=dp[i-1]+[x+[nums[i]] for x in dp[i-1]] return dp[len(nums)-1]
X. Bit Manipulation:


To give all the possible subsets, we just need to exhaust all the possible combinations of the numbers. And each number has only two possibilities: either in or not in a subset. And this can be represented using a bit.
可以根据二进制的思想，比如对于3个元素的集合，000表示一个元素都不选择，001表示选择第一个元素，101表示选择第一个和第三个元素...。因此如果集合大小为n，我们只需要让一个整数从0逐渐增加到2^n-1, 每个整数的二进制形式可以表示一个集合。如果用整数的二进制表示集合，这个算法有个限制，最大能表示集合元素的个数为64（unsigned long long）。如果使用bitmap，然后模拟二进制的加1操作，则对集合大小就没有限制。刚好这一题集合的大小不超过64
https://leetcode.com/problems/subsets/discuss/27288/My-solution-using-bit-manipulation
    vector<vector<int> > subsets(vector<int> &S) {
        sort (S.begin(), S.end());
        int elem_num = S.size();
        int subset_num = pow (2, elem_num);
        vector<vector<int> > subset_set (subset_num, vector<int>());
        for (int i = 0; i < elem_num; i++)
            for (int j = 0; j < subset_num; j++)
                if ((j >> i) & 1)
                    subset_set[j].push_back (S[i]);
        return subset_set;
    }
https://discuss.leetcode.com/topic/2764/my-solution-using-bit-manipulation/5
https://leetcode.com/problems/subsets/discuss/27543/Simple-Java-Solution-Using-Bit-Operations

public List<List<Integer>> subsets(int[] nums) {
    int n = nums.length; // sort first
    List<List<Integer>> subsets = new ArrayList<>();
    for (int i = 0; i < Math.pow(2, n); i++)
    {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++)
        {
            if (((1 << j) & i) != 0)
                subset.add(nums[j]);
        }
        Collections.sort(subset);
        subsets.add(subset);
    }
    return subsets;
}
http://www.cnblogs.com/yuzhangcmu/p/4211815.html
X. DFS+Backtracking
https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51604217
本解法采用回溯算法实现，回溯算法的基本形式是“递归+循环”，正因为循环中嵌套着递归，递归中包含循环，这才使得回溯比一般的递归和单纯的循环更难理解，其实我们熟悉了它的基本形式，就会觉得这样的算法难度也不是很大。原数组中的每个元素有两种状态：存在和不存在。

① 外层循环逐一往中间集合 temp 中加入元素 nums[i]，使这个元素处于存在状态

② 开始递归，递归中携带加入新元素的 temp，并且下一次循环的起始是 i 元素的下一个，因而递归中更新 i 值为 i + 1

③ 将这个从中间集合 temp 中移除，使该元素处于不存在状态

https://www.jianshu.com/p/ac57b9d3d211
  • Backtracking, DFS
  • 首先，数组要排序，在第n层，加入一个元素进入n+1层，删除刚刚加入的元素，加入第n层的第二个元素......
                                   [ ]
                                /   |   \
                             [1]   [2]   [3]
                           /  |     |
                    [1, 2] [1, 3] [2, 3]
                      /
                [1, 2, 3]
  2. Backtracking(the red arrows 红色箭头就是backtracking), DFS（广度优先）
  3. 首先，数组要排序，在第n层，加入一个元素进入n+1层，删除刚刚加入的元素，加入第n层的第二个元素......
Time complexity: O(N * 2^n)
Space complexity: O(2^n)

https://leetcode.com/problems/subsets/discuss/27281/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning
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);
    }
}
https://discuss.leetcode.com/topic/10885/java-subsets-solution
https://discuss.leetcode.com/topic/22636/very-simple-and-fast-java-solution-with-explanation
public List<List<Integer>> subsets(int[] S) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
   
    if(S.length == 0){
        return result;
    }
    
    Arrays.sort(S);
    dfs(S, 0, new ArrayList<Integer>(), result);
    return result;
}

public void dfs(int[] s, int index, List<Integer> path, List<List<Integer>> result){
    result.add(new ArrayList<Integer>(path));
    
    for(int i = index; i < s.length; i++){
        path.add(s[i]);
        dfs(s, i+1, path, result);
        path.remove(path.size()-1);
    }
}

Code from http://blog.csdn.net/u011095253/article/details/9158397
https://leetcode.com/discuss/82960/share-my-12-line-simple-java-code-with-brief-explanations
Why do you have to remove from the list after picking the number at the index?
Because you are picking(trying) each number AT THIS RECURSION LEVEL. One index corresponds to one level. For example, at index 2, the array is like [already-picked-number-0, already-picked-number-1, -(currently-trying)-, not-yet-picked-number-0,...]. Suppose we are trying 45 at "currently-trying", after 45 and the following recursion levels are done, if we do not remove 45 at currently-trying, and add 46 directly, the array will be like [already-picked-number-0, already-picked-number-1, 45, 46,...]. what we want is [already-picked-number-0, already-picked-number-1, 46, not-yet-picked-number-0,...]
dfs. 每个位置都有选与不选两个选项, 也可以看成遍历一棵二叉树, 向左走选, 向右走不选
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null) { return ans; }
        Arrays.sort(nums);  // non-descending order
        dfs(ans, nums, new ArrayList<Integer>(), 0);
        return ans; 
    }
    
    private void dfs(List<List<Integer>> ans, int[] nums, List<Integer> list, int index) {
        if (index == nums.length) { ans.add(new ArrayList<Integer>(list)); return; }
        dfs(ans, nums, list, index+1);  // not pick the number at this index
        list.add(nums[index]);
        dfs(ans, nums, list, index+1);  // pick the number at this index
        list.remove(list.size()-1);
    }
https://leetcode.com/discuss/54541/very-simple-and-fast-java-solution-with-explanation
public List<List<Integer>> subsets(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); List<Integer> each = new ArrayList<>(); helper(res, each, 0, nums); return res; } public void helper(List<List<Integer>> res, List<Integer> each, int pos, int[] n) { if (pos <= n.length) { res.add(each); } for (int i = pos; i < n.length; i++) { each.add(n[i]); helper(res, new ArrayList<>(each), i + 1, n); each.remove(each.size() - 1); } return; }
https://leetcode.com/discuss/11484/accepted-java-solution-dfs
  1. sort the array
  2. start from the end of the array, for each element, do recursive call to get subset for element 'n-1'.
  3. Once get all sebset for n-1, then your subset for n will be : Subset(n)= Subset(n-1)+(n itself) +(add n to Subset(n-1))
  4. at last, don't forget to add [] , from OJ, it counts as one subset as well.
public List <List <Integer>> subsets (int[] S) { if (S == null) return null; Arrays.sort (S); List <List <Integer>> result = new ArrayList <List <Integer>> (); result = getSubSet (S, S.length - 1); result.add (new ArrayList <Integer> ()); return result; } List <List <Integer>> getSubSet (int[] s, int index) { List <List <Integer>> result = new ArrayList <List <Integer>> (); if (index < 0) { return result; } List <List <Integer>> subResult = getSubSet (s, index - 1); result.addAll (subResult); for (int i = 0; i < subResult.size (); i++) { List <Integer> bList = new ArrayList <> (); bList.addAll (subResult.get (i)); bList.add (s[index]); result.add (bList); } result.add (Arrays.asList (s[index])); return result; }
http://blog.welkinlan.com/2015/07/17/subsets-i-subsets-ii-leetcode-java/
每当我们添加了一个元素，都是一个新的子集。那么我们怎么保证不会出现重复集合呢。我们引入一个int pos用来记录此子集的起点在哪，比如当pos = 1的时候就是从第二个元素往后循环添加元素（0 base）,每次当此层用了第i个元素，那么下一层需要传入下一个元素的位置i+1 除此之外，当循环结束要返回上一层dfs的时候我们需要把这一层刚添加元素删去。
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
       ArrayList<Integer> tmp = new ArrayList<Integer>();
       Arrays.sort(S);
       res.add(tmp);
       dfs(res,tmp,S,0);
       return res;
    }
 
    public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, int[] S, int pos){
        for(int i=pos; i<=S.length-1;i++){
            tmp.add(S[i]);
            res.add(new ArrayList<Integer>(tmp));
            dfs(res,tmp,S,i+1);
            tmp.remove(tmp.size()-1);
        }
    }


http://www.cnblogs.com/TenosDoIt/p/3451902.html
 5     vector<vector<int> > subsets(vector<int> &S) {
 6         // IMPORTANT: Please reset any member data you declared, as
 7         // the same Solution instance will be reused for each test case.
 8         //先排序，然后dfs每个元素选或者不选，最后叶子节点就是所有解
 9         res.clear();
10         sort(S.begin(), S.end());
11         vector<int>tmpres;
12         dfs(S, 0, tmpres);
13         return res;
14     }
15     void dfs(vector<int> &S, int iend, vector<int> &tmpres)
16     {
17         if(iend == S.size())
18             {res.push_back(tmpres); return;}
19         //选择S[iend]
20         tmpres.push_back(S[iend]);
21         dfs(S, iend+1, tmpres);
22         tmpres.pop_back();
23         //不选择S[iend]
24         dfs(S, iend+1, tmpres);
25     }
http://www.cnblogs.com/springfor/p/3879830.html
一个思路就是套用combination的方法，其实combination那道题就是在求不同n下的subset，这里其实是要求一个集合罢了。
例如k=3，n=1，用combination那道题的方法求得集合是[[1], [2], [3]]；
    k=3, n=2, 用combination那道题的方法求得集合是[[1, 2], [1, 3], [2, 3]]
    k=3, n=3, 用combination那道题的方法求得集合是[[1,2,3]]
1 public static void dfs(int[] S, int start, int len, ArrayList<Integer> item,ArrayList<ArrayList<Integer>> res){
 2         if(item.size()==len){
 3             res.add(new ArrayList<Integer>(item));
 4             return;
 5         }
 6         for(int i=start; i<S.length;i++){
 7             item.add(S[i]);
 8             dfs(S, i+1, len, item, res);
 9             item.remove(item.size()-1);
10         }
12     }
14     public static ArrayList<ArrayList<Integer>> subsets(int[] S) {
15         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
16         ArrayList<Integer> item = new ArrayList<Integer>();
17         if(S.length==0||S==null)
18             return res;
20         Arrays.sort(S);
21         for(int len = 1; len<= S.length; len++)
22             dfs(S,0,len,item,res);
23             
24         res.add(new ArrayList<Integer>());
25         
26         return res;
27     }
http://pisxw.com/algorithm/Subsets.html
public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(S==null || S.length==0) return res; Arrays.sort(S); res.add(new ArrayList<Integer>()); for(int i=1;i<=S.length;i++) { helper(S,i,0,new ArrayList<Integer>(), res); } return res; } private void helper(int[] S, int k, int start, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res) { if(item.size()==k) { res.add(new ArrayList<Integer>(item)); return; } for(int i=start;i<S.length;i++) { item.add(S[i]); helper(S,k,i+1,item,res); item.remove(item.size()-1); } }
http://www.binglu.me/subsets-leetcode/
http://allenlipeng47.com/PersonalPage/index/view/196/nkey

https://discuss.leetcode.com/topic/27405/haven-t-see-dp-solution-here-it-is
def subnets(nums):
    nums.sort()
    dp={}
    dp[0]=[[],[nums[0]] ] 
    
    for i in range(1,len(nums)):
        dp[i]=dp[i-1]+[x+[nums[i]] for x in dp[i-1]]
    return dp[len(nums)-1]
X. Follow up
https://discuss.leetcode.com/topic/32240/what-if-the-given-array-is-non-distinct-integers
What if the given array is non distinct integers?
public static List<List<Integer>> subsets2(int[] nums) {
 List<List<Integer>> result = new ArrayList<List<Integer>>();
 List<Integer> item = new ArrayList<Integer>();
    // add empty set
 result.add(item); 

 Arrays.sort(nums);

 int repeat = 0;

 for (int i = 0; i < nums.length; i++) {
  int n = result.size();
  if (i > 0 && nums[i] == nums[i - 1]) {
   repeat++;
  } else {
   repeat = 0;
  }
  for (int j = repeat; j < n; j++) {
   item = new ArrayList<Integer>(result.get(j));
   item.add(nums[i]);
   result.add(item);
  }
 }
 return result;
}
http://blog.hyoung.me/cn/2017/02/subsets/
给定一组不重复的元素，找出所有的子集，且要求子集内为非递减排序。
像这种需要穷举出所有可能性的问题，一般都是通过 DFS 来解决。假设给定的元素集合为[1,2,3]，整个 DFS 搜索过程如下图所示
DFS Search in [1,2,3]DFS Search in [1,2,3]
其中实线代表进入到下一个递归函数当中，虚线代表从一个递归函数中返回。
配合着这个简单的例子，我们可以总结出递归的三要素
  1. 递归的初始化：当前子集为空，可搜索集合为给定的元素集合
  2. 递归的出口：当前可搜索的集合为空
  3. 递归的分解：将当前可搜寻集合中的第一个元素加入到当前子集当中，然后将可搜寻集合设为余下的元素集合，进入到下一层递归。当完成了对包含该元素所有子集的搜索之后，将该元素从当前子集中删去，然后将当前可搜寻集合中的下一个元素加入当前子集中，再次进入到下一层递归当中。如此循环遍历当前可搜索集合中的所有元素。
此外，因为要保证子集中的非递减排序，我们可以先对整个数组进行排序。









1



2



3



4



5



6



7



8



9



10



11



12



13



14



15



16



17



18



19



vector<vector<int> > subsets(vector<int> &nums) {



vector<vector<int>> results;



vector<int> subset;



sort(nums.begin(), nums.end());



dfsHelper(nums, 0, subset, results);







return results;



}







void dfsHelper(vector<int>& nums, int startIndex, vector<int>& subset, 



vector<vector<int>>& results) {



results.push_back(subset);







for (int i = startIndex; i < nums.size(); ++i) {



subset.push_back(nums[i]);



dfsHelper(nums, i + 1, subset, results);



subset.pop_back();



}



}

虽然分析的时候啰啰嗦嗦说了一大堆，但实现起来却十分简洁。我们只需要记录当前可搜索元素的起始坐标，并维护一个当前子集即可。值得注意的是，每一次进入到递归时，我们都有了一个新的子集，所以需要把它加入到最终的结果当中。
X. https://www.bbsmax.com/A/D854p0w5Eg/
请编写一个方法，返回某集合的所有非空子集。
给定一个int数组A和数组的大小int n，请返回A的所有非空子集。保证A的元素个数小于等于20，且元素互异。各子集内部从大到小排序,子集之间字典逆序排序，见样例。
测试样例：
[123,456,789]
返回：{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}

答案和思路：还是利用来一个插入一个的思想来做。但是因为要全部逆序，所以，要注意插入的方式是从后往前，而且是在原有集合的基础上插入的时候把他放到他前面。

    public static ArrayList<ArrayList<Integer>> getSubsets(int[] a, int n) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        Arrays.sort(a);
        for (int i = n - 1; i >= 0; --i) {
            ArrayList<ArrayList<Integer>> temp = new ArrayList();
            for (ArrayList<Integer> list : res) {
                ArrayList<Integer> tempList = new ArrayList(list);
                ArrayList<Integer> list2 = new ArrayList(list);
                tempList.add(a[i]);
                temp.add(tempList);
                temp.add(list2);
            }
            ArrayList<Integer> now = new ArrayList();
            now.add(a[i]);
            temp.add(now);
            res = new ArrayList(temp);
            System.out.println(res);
        }
        return res;
    }


at
Labels: , , , , , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts