屁儿擦爽a
2021-10-14 16:58
采纳率: 100%
浏览 78
已结题

leetcode 78. 子集 这方法怎么得到结果的啊,没看懂

img


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]);    // t.add(nums[0]) 
        System.out.print(cur);
        dfs(cur+1, nums);
        t.remove(t.size() - 1);
        dfs(cur+1,nums);

    }
}
  • 好问题 提建议
  • 收藏

2条回答 默认 最新

  • qq_34370249 2021-10-14 17:18
    已采纳

    递归调用,
    解释一下dfs方法
    参数 cur 当前便拎数组的下标,nums数组
    if -》如果,cur和数组的长度一致,退出,(这是递归退出的条件,也就是说,当数组的长度== 0 或者 cur走到了数组的最后一位时,退出)
    t.add -> 将下标为cur的元素,放在t中
    dfs 重复 之前的步骤,(递归调用)
    t.remove -> 移除t中的最后一个元素
    dfs 重复之前的步骤,(递归调用)

    举个例子
    数组[1,2,3],来说
    第一次进入dfs方法时

    1. cur = 0
      0 != 3
      t.add(1); // t = {1}
      进入dfs方法
      1. cur = 1
        1 != 3
        t.add(2)
        进入dfs方法
         cur = 2
         3. 2 != 3
          t.add(3)  // t = {1,2,3}
         进入dfs方法
           4. 3 ==3
               把这个t放入ans中, 此时 ans = {(1,2,3)}
               退出,回到第三步
         删除t中的最后一个元素
         t.remove() // t = {1,2}
         在进入dfs方法,
         此时cur ==3
         将{1,2}放入ans
        
        重复以上步骤,就出来了
    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • 走一步-再走一步 2021-10-15 13:52

    思路:
    因为是返回所有的子集,那么等价于遍历 所有的组合,而所有的组合考虑到每一个数字有2中可能
    1:包含该数字 ,2:不包含该数字
    针对长度为3的数组 1 2 3
    针对第一位1 两种可能
    1-> 包含1: 结果就是 1 + 【2,3】的所有可能组合
    2-> 不包含1,结果就是 [2,3]的所有可能组合 依次类推
    而所有组合 递归很容易就能实现
    定义 dfs(cur,int[] nums,boolean ) 数组,其中cur 表示针对第cur位数字 ,boolean 表示是否包含该位的所有组合
    dfs(cur,int[] nums)数组,其中cur 表示针对第cur位数字,的所有组合
    dfs(cur,int[] nums) = dfs(cur-1,nums,false) + dfs(cur-1,nums,true)的所有组合
    因为dfs(cur-1,nums,false) 不包含第cur-1位数字,dfs(cur-1,nums,true) 包含第cur-1位数字,因此一定没有交集不需要去重

    //t 存储已经选中的数字
    public void dfs(int cur, int[] nums){
           // 选到最后一位,表明已经选完了
            if(cur == nums.length){   
                ans.add(new ArrayList<Integer>(t));
                return;
            }
    
    // 这2行表明选中 cur的这一位 ,在往后面遍历 等价于分支 dfs(cur-1,nums,true)
            t.add(nums[cur]);    // 步骤1 
            dfs(cur+1, nums);
    
            // 这里要走 不包含cur的这一位,而选中的列表中已经选中了这一位,因此把该位移除
            t.remove(t.size() - 1);
            // dfs(cur-1,nums,false) 等价于分支
            dfs(cur+1,nums);
     
        }
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题