056子集

子集题目链接https://leetcode.cn/problems/subsets/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListListInteger subsets(int[] nums) { ListListInteger ans new ArrayList(); ListInteger output new ArrayList(); backtrack(nums, output, 0, nums.length, ans); return ans; } public void backtrack(int[] nums, ListInteger output, int cur, int n, ListListInteger ans){ if(cur n){ ans.add(new ArrayList(output)); return; } //不选取当前位置的元素 backtrack(nums, output, cur1, n, ans); //选取当前位置的元素 output.add(nums[cur]); backtrack(nums, output, cur1, n, ans); //回溯 output.remove(output.size()-1); }分析代码的时间复杂度为O(n*2^n)空间复杂度为O(n)。解题思路对于nums数组的每一个元素只有两种情况选取和不选取,递归回溯即可简单解决此问题。看了官方题解后的解答//方法一迭代法实现子集枚举 //时间复杂度O(n*2^n) //空间复杂度O(1) public ListListInteger subsets(int[] nums) { int n nums.length; ListListInteger ans new ArrayList(); int max 1 n;//计算2^n for(int i0; imax; i){ ans.add(new ArrayList()); for(int j0; jn; j){ if(((1 j) i) ! 0){ ans.get(i).add(nums[j]); } } } return ans; } //方法二递归法实现子集枚举方法二与我的解答基本一致 //时间复杂度O(n*2^n)一共2^n个状态每种状态需要 O(n) 的时间来构造子集。 //空间复杂度O(n) public ListListInteger subsets(int[] nums) { ListListInteger ans new ArrayList(); ListInteger output new ArrayList(); backtrack(nums, output, 0, ans); return ans; } public void backtrack(int[] nums, ListInteger output, int cur, ListListInteger ans){ if(cur nums.length){ ans.add(new ArrayList(output)); return; } //不选取当前位置的元素 backtrack(nums, output, cur1, ans); //选取当前位置的元素 output.add(nums[cur]); backtrack(nums, output, cur1, ans); //回溯 output.remove(output.size()-1); }分析​ 1、方法一的解题思路对于一个长度为n的集合它的子集一共有2^n 种可能对于数组每一个位置上的元素只有两种状态分别为在子集中和不在子集中我们让0代表不在子集中让1代表在子集中这样对于任意一个子集都可以用一串长度为n的01序列来表示根据这个发现我们只需列举0到2^n-1这些数字他们对应的二进制就可以代表一个子集我们只需根据二进制每一位是0还是1来决定nums数组在此位置的元素要不要加入当前子集即可。​ 2、方法二的解题思路与我的解答一致。总结本题可采用迭代和递归两种方法解题。迭代法根据每个位置上的元素只有两种状态将子串与二进制序列联系起来。注意递归方法的时间复杂度计算。