代码随想录 Q76.子集

题目要求返回一个整数数组所有可能的子集。子集问题处理的是组合问题不受排列顺序的影响只关心哪些数字被选中不关心选中的顺序。因此子集问题需要通过startIndex强制规定下一层递归只能从当前元素的后面的元素中选择。已选过的元素不能再回头选否则就会产生重复。思路1.子集问题与组合问题、分割问题不同如果把这些问题都抽象为一棵树的话组合问题和分割问题都是收集树的叶子节点而子集问题是收集树的所有节点。2.子集问题和组合问题的集合都是无序的也就是说子集{12}和子集{21}是一样的。3.因为子集问题是无序的所以取过的元素不会重复取所以写回溯算法的时候for就要从startIndex开始而不是从0开始如果是求排列的问题则应该从0开始因为集合是有序的{12}和{21}是两个集合。以nums [1,2,3]为例求子集过程可抽象为如下树形结构。在遍历树的过程中把遍历到的节点记录下来可以得到要求的子集集合。回溯三部曲1.递归函数参数1全局变量path为子集收集元素二维数组res存放各个子集也可以放到递归函数参数里。ListListInteger res new ArrayList(); LinkedListInteger path new LinkedList();2递归函数参数题目所给的整数数组nums还需要一个参数记录本层递归的集合从哪里开始遍历即下一层递归搜索的起始位置定义为int型的startIndex。private void backTracking(int[] nums,int startIndex)2.递归终止条件从图中可以看出剩余集合为空时到达叶子节点。startIndex已经大于数组的长度时就终止因为没有元素可取。可以不需要加终止条件因为startIndex nums.size()本层for循环本来也结束了。if(startIndex nums.length){ return; }3.单层搜索逻辑求取子集问题不需要任何剪枝因为求子集就是要遍历整棵树单层递归逻辑的代码如下所示。for(int i startIndex;i nums.length;i){ path.add(nums[i]); backTracking(nums,i 1); path.removeLast(); }附代码class Solution { ListListInteger res new ArrayList(); LinkedListInteger path new LinkedList(); public ListListInteger subsets(int[] nums) { backTracking(nums,0); return res; } private void backTracking(int[] nums,int startIndex){ // 收集子集要放到终止条件的上面否则会漏掉自己。 res.add(new ArrayList(path)); if(startIndex nums.length){ return; } // 单个集合的组合问题从startIndex往后遍历 for(int i startIndex;i nums.length;i){ path.add(nums[i]); backTracking(nums,i 1); path.removeLast(); } } }