[Leetcode][第78题][JAVA][子集][位运算][回溯]

男娘i 2022-12-08 14:29 149阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 1. 位运算 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

**复杂度**  
![在这里插入图片描述][20200920130142605.png_pic_center]

class Solution { 
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> subsets(int[] nums) { 
            int n = nums.length;
            for (int mask = 0; mask < (1 << n); ++mask) { 
                t.clear();
                for (int i = 0; i < n; ++i) { 
                    if ((mask & (1 << i)) != 0) { 
                        t.add(nums[i]);
                    }
                }
                ans.add(new ArrayList<Integer>(t));
            }
            return ans;
        }
    }

###### 2. 回溯 begin标记 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][20200920130253685.png_pic_center]

class Solution { 
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> subsets(int[] nums) { 
            dfs(0, nums);
            return ans;
        }
    
        public void dfs(int cur, int[] nums) { 
            if (cur == nums.length) { 
                ans.add(new ArrayList<Integer>(t));
                return;
            }
            t.add(nums[cur]);
            dfs(cur + 1, nums);
            t.remove(t.size() - 1);
            dfs(cur + 1, nums);
        }
    }

#### 【总结】 ####

###### 1. 什么时候用或者不用used数组？ ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

###### 2.位运算相关 ######

![在这里插入图片描述][20200920130522458.png_pic_center]

###### 3.回溯相关题目 ######

[\[Leedcode\]\[JAVA\]\[第46题\]\[全排列\]\[回溯算法\]][Leedcode_JAVA_46]  
[\[Leetcode\]\[第81题\]\[JAVA\]\[N皇后问题\]\[回溯算法\]][Leetcode_81_JAVA_N]  
[\[Leetcode\]\[第60题\]\[JAVA\]\[第k个排列\]\[回溯\]\[DFS\]\[剪枝\]][Leetcode_60_JAVA_k_DFS]  
[\[Leetcode\]\[第39题\]\[JAVA\]\[组合总和\]\[回溯\]\[dfs\]\[剪枝\]][Leetcode_39_JAVA_dfs]  
[\[Leetcode\]\[第40题\]\[JAVA\]\[数组总和2\]\[回溯\]\[剪枝\]][Leetcode_40_JAVA_2]  
[\[Leetcode\]\[第216题\]\[JAVA\]\[数组之和3\]\[回溯\]][Leetcode_216_JAVA_3]  
[\[Leetcode\]\[第79题\]\[JAVA\]\[单词搜索\]\[DFS\]\[回溯\]][Leetcode_79_JAVA_DFS]  
[\[Leetcode\]\[第17题\]\[JAVA\]\[电话号码的字母组合\]\[回溯\]][Leetcode_17_JAVA]  
[\[Leetcode\]\[第93题\]\[JAVA\]\[复原IP地址\]\[剪枝\]\[回溯\]][Leetcode_93_JAVA_IP]  
[\[Leetcode\]\[第679题\]\[JAVA\]\[24点游戏\]\[回溯\]\[暴力\]][Leetcode_679_JAVA_24]

转载链接：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e99d82c671e44a7dae4eab6f0b988d72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ce829b22830e44e8ac9e119d106a2d72.png
[20200920130142605.png_pic_center]: /images/20221123/b1cc3340cb2a40c5b9cb5524bcef6be9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/ea1b68952d3d4c3dba6f4d0485338f5c.png
[20200920130253685.png_pic_center]: /images/20221123/b2933d5bb65e4c9883713b20f88ffa47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/36678a97fb674e7199ca8bac20e81801.png
[20200920130522458.png_pic_center]: /images/20221123/b9b652f3a8764ec6ad8c295968986f83.png
[Leedcode_JAVA_46]: https://blog.csdn.net/dadongwudi/article/details/105760561
[Leetcode_81_JAVA_N]: https://blog.csdn.net/dadongwudi/article/details/108379661
[Leetcode_60_JAVA_k_DFS]: https://blog.csdn.net/dadongwudi/article/details/108419966
[Leetcode_39_JAVA_dfs]: https://blog.csdn.net/dadongwudi/article/details/108485315
[Leetcode_40_JAVA_2]: https://blog.csdn.net/dadongwudi/article/details/108507750
[Leetcode_216_JAVA_3]: https://blog.csdn.net/dadongwudi/article/details/108530515
[Leetcode_79_JAVA_DFS]: https://blog.csdn.net/dadongwudi/article/details/108560469
[Leetcode_17_JAVA]: https://blog.csdn.net/dadongwudi/article/details/108235943
[Leetcode_93_JAVA_IP]: https://blog.csdn.net/dadongwudi/article/details/107924709
[Leetcode_679_JAVA_24]: https://blog.csdn.net/dadongwudi/article/details/108164797