2019獨角獸企業(yè)重金招聘Python工程師標準>>>

問題：

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

Note:?The solution set must not contain duplicate subsets.

For example,
If?nums?=?[1,2,3], a solution is:

[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] ]

解決：

① 使用dfs，使用一個變量來記錄路徑，每遍歷到一個元素即表示找到一條路徑，將其加入子集中。?

class Solution {//3ms
? ? public List<List<Integer>> subsets(int[] nums) {
? ? ? ? List<List<Integer>> res = new ArrayList<>();
? ? ? ? List<Integer> list = new ArrayList<>();
? ? ? ? Arrays.sort(nums); //使子集內(nèi)有序
? ? ? ? dfs(nums,0,list,res);
? ? ? ? return res;
? ? }
? ? public void dfs(int[] nums,int i,List<Integer> list,List<List<Integer>> res){
? ? ? ? res.add(new ArrayList<Integer>(list));
? ? ? ? for (int j = i;j < nums.length ;j ++ ) {
? ? ? ? ? ? list.add(nums[j]);
? ? ? ? ? ? dfs(nums,j + 1,list,res);
? ? ? ? ? ? list.remove(list.size() - 1);
? ? ? ? }
? ? }
}

② 如果不使用排序的話，耗時會減少，但是子集內(nèi)會變?yōu)闊o序的。

class Solution {//2ms
? ? public List<List<Integer>> subsets(int[] nums) {
? ? ? ? List<List<Integer>> res = new ArrayList<>();
? ? ? ? List<Integer> list = new ArrayList<>();
? ? ? ? //Arrays.sort(nums);
? ? ? ? dfs(nums,0,list,res);
? ? ? ? return res;
? ? }
? ? public void dfs(int[] nums,int i,List<Integer> list,List<List<Integer>> res){
? ? ? ? res.add(new ArrayList<Integer>(list));
? ? ? ? for (int j = i;j < nums.length ;j ++ ) {
? ? ? ? ? ? list.add(nums[j]);
? ? ? ? ? ? dfs(nums,j + 1,list,res);
? ? ? ? ? ? list.remove(list.size() - 1);
? ? ? ? }
? ? }
}

③ 非遞歸方法。http://blog.csdn.net/happyaaaaaaaaaaa/article/details/51604217

這種方法是一種組合的方式：

1） 最外層循環(huán)逐一從 nums 數(shù)組中取出每個元素 num

2） 內(nèi)層循環(huán)從原來的結(jié)果集中取出每個中間結(jié)果集，并向每個中間結(jié)果集中添加該 num 元素

3） 往每個中間結(jié)果集中加入 num

4） 將新的中間結(jié)果集加入結(jié)果集中

class Solution {//2ms
? ? public List<List<Integer>> subsets(int[] nums) {
? ? ? ? List<List<Integer>> res = new ArrayList<>();
? ? ? ? res.add(new ArrayList<Integer>());
? ? ? ? for (int num : nums) { ?// ①從數(shù)組中取出每個元素
? ? ? ? ? ? int size = res.size();
? ? ? ? ? ? for (int i = 0; i < size; i++) {
? ? ? ? ? ? ? ? List<Integer> temp = new ArrayList<>(res.get(i)); ?// ②逐一取出中間結(jié)果集
? ? ? ? ? ? ? ? temp.add(num); ?// ③將 num 放入中間結(jié)果集
? ? ? ? ? ? ? ? res.add(temp); ?// ④加入到結(jié)果集中
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
}

④ 還可以使用位操作來解決。

對于數(shù)列{1 , 2 , 3 }的子集的個數(shù) = 2^3 .
原因：
對于子集中的每一個數(shù)字，都有取或者不取兩種情況，所以自己的個數(shù)：
total = 2 * 2 * 2 = 2 ^ 3 = { { } , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }
可以用一個下標0和1表示是否選擇該數(shù)字，0表示未選擇，1表示選中，那么每一組3個0和1的組合表示一種選擇，3位共有8種選擇，分別是：?
0) 0 0 0 ?-> 不取3 , 不取2 , 不取1 = { }?
1) 0 0 1 ?-> 不取3 , 不取2 , ? 取1 = ?{1 }?
2) 0 1 0 ?-> 不取3 , ? 取2 , 不取1 = { 2 }?
3) 0 1 1 ?-> 不取3 , ? 取2 , ? 取1 = { 1 , 2 }?
4) 1 0 0 ?-> ? 取 3, 不取2 , 不取1 = { 3 }?
5) 1 0 1 ?-> ? 取 3, 不取2 , 不取1 = { 1 , 3 }?
6) 1 1 0 ?-> ? 取 3, ? 取2 , 不取1 = { 2 , 3 }?
7) 1 1 1 ?-> ? 取 3, ? 取2 , ? 取1 = { 1 , 2 , 3 }?

對于(i & (1 << j)) != 0，i = {0，1，2，3，4，5，6，7}，j = {0，1，2}。

當取第0個位置的元素時：
(i & (1 << 0)) != 0 ?==> 向下標最低位為1的鏈表中插入nums[0] ==> i = {1，3，5，7}

當取第1個位置的元素時：
(i & (1 << 1)) != 0 ==> 向下標右邊數(shù)第二位為1的鏈表中插入nums[1] ==> i = {2，3，6，7}

當取第2個位置的元素時：
(i & (1 << 2)) != 0 ==> 向下標右邊數(shù)第二位為3的鏈表中插入nums[2] ==> i = {4，5，6，7}

時間復(fù)雜度為：O(n*2^n)，對于每個輸入元素都遍歷其解集長度即2^n.

class Solution{
? ? public List<List<Integer>> subsets(int[] nums) {
? ? ? ? Arrays.sort(nums);
? ? ? ? int totalNumber = 1 << nums.length; //total = (int)Math.pow(2,nums.length);
? ? ? ? List<List<Integer>> res = new ArrayList<List<Integer>>(totalNumber);
? ? ? ? for (int i = 0; i < totalNumber; i ++) {
? ? ? ? ? ? List<Integer> tmp = new LinkedList<Integer>();
? ? ? ? ? ? for (int j = 0; j < nums.length; j ++) {
? ? ? ? ? ? ? ? if ((i & (1 << j)) != 0) {
? ? ? ? ? ? ? ? ? ? tmp.add(nums[j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? res.add(tmp);
? ? ? ? }
? ? ? ? return res;
? ? }
}

轉(zhuǎn)載于:https://my.oschina.net/liyurong/blog/1538449

總結(jié)

以上是生活随笔為你收集整理的给定数组的子集 Subsets的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。