leetcode78.Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums &＃61; [1,2,3], a solution is:

[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
] 蛮简单的题目&＃xff0c;用递归就能完成&＃xff1a;当前元素&＃xff1a;取/不取&＃xff0c;再递归到下一个元素。

public List> subsets(int[] nums) {List> result&＃61;new ArrayList>();List list&＃61;new ArrayList<>();helper(nums, 0,result,list);return result;
}public void helper(int[] nums,int index,List> result,List list){if(index&＃61;&＃61;nums.length){result.add(list);return;}List newList&＃61;new ArrayList<>(list);helper(nums, index&＃43;1, result, newList);newList&＃61;new ArrayList<>(list);newList.add(nums[index]);helper(nums, index&＃43;1, result, newList);
}还有大神没有用递归&＃xff0c;思路也很好。

起始subset集为&＃xff1a;[]
添加S0后为&＃xff1a;[], [S0]
添加S1后为&＃xff1a;[], [S0], [S1], [S0, S1]
添加S2后为&＃xff1a;[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]
红色subset为每次新增的。显然规律为添加Si后&＃xff0c;新增的subset为克隆现有的所有subset&＃xff0c;并在它们后面都加上Si。 这样的话就只要迭代就能解决了。

public class Solution {public List> subsets(int[] S) {List> res &＃61; new ArrayList<>();res.add(new ArrayList()); Arrays.sort(S);for(int i : S) {List> tmp &＃61; new ArrayList<>();for(List sub : res) {List a &＃61; new ArrayList<>(sub);a.add(i);tmp.add(a);}res.addAll(tmp);}return res;}
}除这两种方法之外&＃xff0c;大神还有另外一种与众不同的方法&＃xff1a;bit-manipulation&＃xff01;

{1 , 2 , 3 }的子集个数 &＃61; 2^3 .为什么? 考虑到数组中每个元素是否取的情况1 -> 取 or 不取 &＃61; 2 2 -> 取 or 不取 &＃61; 2 3 -> 取 or 不取 &＃61; 2 所以&＃xff0c;总的情况 &＃61; 2*2*2 &＃61; 2^3 &＃61; { { } , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }让我们用 1 和 0 来表示取或者不取。数组中有三个元素&＃xff0c;因此需要3个bit&＃xff0c;其中低位->高位表示nums[0]~nums[n]
取 &＃61; 1
不取 &＃61; 00) 0 0 0 -> 不取 3 , 不取 2 , 不取 1 &＃61; { }
1) 0 0 1 -> 不取 3 , 不取 2 , 取 1 &＃61; {1 }
2) 0 1 0 -> 不取 3 , 取 2 , 不取 1 &＃61; { 2 }
3) 0 1 1 -> 不取 3 , 取 2 , 取 1 &＃61; { 1 , 2 }
4) 1 0 0 -> 取 3 , 不取 2 , 不取 1 &＃61; { 3 }
5) 1 0 1 -> 取 3 , 不取 2 , 取 1 &＃61; { 1 , 3 }
6) 1 1 0 -> 取 3 , 取 2 , 不取 1 &＃61; { 2 , 3 }
7) 1 1 1 -> 取 3 , 取 2 , 取 1&＃61; { 1 , 2 , 3 } 在上面的逻辑中&＃xff0c;只有当 (j>>i)&1 &＃61;&＃61;true {其中 j ∈ {0,1,2,3,4,5,6,7}&＃xff0c;i 是 nums[]的索引} 时&＃xff0c;才进行 Insert S[i] 的操作。
因此&＃xff0c;数字1只有当最右bit是1的时候才被插入&＃xff0c;&＃xff08; j &＃61; 1,3,5,7 时&＃xff09;
数字2只有当第二右bit是1的时候才被插入&＃xff0c;( j &＃61; 2,3,6,7 时&＃xff09;
数字3只有当第三右bit是1的时候才被插入&＃xff0c;( j &＃61; 4,5,6,7 时&＃xff09;该解法时间复杂度 : O(n * 2^n)

public List> subsets(int[] S) {Arrays.sort(S);int totalNumber &＃61; 1 <> collection &＃61; new ArrayList>(totalNumber);for (int i&＃61;0; i set &＃61; new LinkedList();for (int j&＃61;0; j}