当前位置: 首页 > 工具软件 > dfs > 使用案例 >

DFS常见算法

仉刚洁
2023-12-01

DFS

78. 子集

难度中等1101

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

方法一:迭代

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        // 枚举0~2^n-1,也就是子集的个数
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < (1 << n); i++){
            List<Integer> t = new ArrayList<>();
            // 通过求出i的二进制位上的1来表示是否去对应j位置上的数字
            for(int j = 0; j < n; j++){
                if((i >> j & 1) == 1){
                    t.add(nums[j]);
                }
            }
            res.add(t);
        }
        return res;
    }
}

方法二:回溯

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        //dfs,对于每个位置有两种可能性,一个是添加进子集,不加入子集
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(res,path,n,0,nums);
        return res;
    }
    private void dfs(List<List<Integer>> res, Deque<Integer> path, int n,int pos,int[] nums){
        if(pos == n){
            res.add(new ArrayList(path));
            return;
        }
        path.addLast(nums[pos]);
        dfs(res,path,n,pos+1,nums);
        path.removeLast();
        dfs(res,path,n,pos+1,nums);
    }
}

90. 子集 II

难度中等523

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例 1:

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

方法一:回溯

class Solution {
    List<List<Integer>> res = null;
    boolean[] st;
    Deque<Integer> path = null;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        res = new ArrayList<>();
        path = new LinkedList<>();
        st = new boolean[n];
        dfs(nums,n,0);
        return res;
    }
    private void dfs(int[] nums, int n, int idx){
        if(idx == n){
            res.add(new ArrayList<>(path));
            return;
        }
        dfs(nums,n,idx+1);
        if(idx > 0 && !st[idx-1] && nums[idx] == nums[idx-1]){
            return;
        }
        st[idx] = true;
        path.addLast(nums[idx]);
        dfs(nums,n,idx+1);
        st[idx] = false;
        path.removeLast();
    }
}

方法二:迭代

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < (1 << n); i++){
            List<Integer> t = new ArrayList<>();
            boolean flag = false;
            for(int j = 0; j < n; j++){
                if((i >> j & 1) == 1){
                    // 当前值x,如果在x前面存在与x相同的y,并且没有取到,
                    // 那么取x的时候结果就包含在y的子集中
                    // 这是为什么呢,例如 nums[1,2,2],第3个子集为取0,1位置上的数,也就是{1,2}
                    // 然后到了第5个子集,这个时候取0,2位置上的数,也是{1,2};
                    // 可以看到第3个子集已经包合了第5个子集
                    if(j > 0 && (i >> j-1 & 1) == 0 && nums[j] == nums[j-1]){
                        flag = true;
                        break;
                    }
                    t.add(nums[j]);
                }
            }
            if(!flag){
                res.add(t);
            }
        }
        return res;
    }
}
 类似资料: