53.子集（打印树的过程节点）

53.子集（打印树的过程节点）

解题思路：遍历开始的节点序号，节点序号前的元素不会被选取—妙不可言

class Solution {
    List> result = new ArrayList<>();// 存放符合条件结果的集合
    linkedList path = new linkedList<>();// 用来存放符合条件结果
    public List> subsets(int[] nums) {
        if (nums.length == 0){
            result.add(new ArrayList<>());
            return result;
        }
        subsetsHelper(nums, 0);
        return result;
    }


//先加的下一次的序号，再存放本次的结果，再判断下一次的序号是否合法
    private void subsetsHelper(int[] nums, int startIndex){

        //「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        //存放上一次的path列表
        result.add(new ArrayList<>(path));

       //终止条件，判断本次的序号是否合法（可以不加，因为i>=nums.length进不去for循环）
        if (startIndex >= nums.length){ 
            return;
        }

       //针对开始的序号进行遍历--序号之前的元素都不会被用上
        for (int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            //回溯，删除本次开始的序号，从新的序号开始
            path.removeLast();
        }
    }
}

官方题解–想法：这个位置选与不选—难理解但是妙

class Solution {
    List t = new ArrayList();
    List> ans = new ArrayList>();

    public List> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList(t));
            return;
        }

        //思路：到达每一个元素位置都会进行判断“取还是不取”--我们一定会从头到尾遍历这个数组一遍（不管我们选择多少个元素放入列表中）----复杂度=总的组合情况*数组长度
        
        // 情况1(数组判断长度cur)：:放在cur这个位置，继续向下一位置递归判断
        t.add(nums[cur]);
        dfs(cur + 1, nums);

        //情况2(数组判断长度cur)：不放在cur这个位置，继续向下一位置递归判断
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

多加一步保证同层不会出现相同的数字----大前提：数组已经排序过了的

class Solution {

  List> res = new ArrayList<>();
  linkedList path = new linkedList<>();
  
  public List> subsetsWithDup( int[] nums ) {

    //去重需要对数组进行排序
    Arrays.sort( nums );
    subsetsWithDupHelper( nums, 0 );
    return res;
  }


  private void subsetsWithDupHelper( int[] nums, int start ) {
        res.add( new ArrayList<>( path ) );

       //终止条件，判断本次的序号是否合法（可以不加，因为i>=nums.length进不去for循环）
        if (start >= nums.length){ 
            return;
        }

        for ( int i = start; i < nums.length; i++ ) {
            // 跳过当前树层使用过的、相同的元素（同层不能出现相同的数字，但是递归纵向可以使用相同的数字）
            if ( i > start && nums[i - 1] == nums[i] ) {
                continue;
            }
            path.add( nums[i] );
            subsetsWithDupHelper( nums, i + 1 );
            path.removeLast();
        }
  }

}