欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

DFS中关于全排列、组合、子集中有重复数字去重的问题

程序员文章站 2022-03-10 17:16:02
写在前面:关于何时用used数组储存是否访问过以及何时用begin作为循环的起始值,请参考前一篇博客一、全排列1.没有重复数字Leetcode46.全排列:给定一个没有重复数字的序列,返回其所有可能的全排列。解法很简单,画出树状结构,经典的dfs问题,代码如下。import java.util.ArrayList;import java.util.List;public class Solution { public static List

写在前面:关于何时用used数组储存是否访问过以及何时用begin作为循环的起始值,请参考前一篇博客

一、全排列

1.没有重复数字

Leetcode46.全排列:给定一个没有重复数字的序列,返回其所有可能的全排列。

解法很简单,画出树状结构,经典的dfs问题,代码如下。

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static List<List<Integer>> permute(int[] nums) {
        if(nums.length==0){
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> l = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        helper(result,l,nums,0,used);
        return result;
    }

    public static void helper(List<List<Integer>> result,List<Integer> l,int[] nums,int index,boolean[] used){

        if(nums.length==index){
            result.add(new ArrayList<>(l));//注意这里如果直接传入l的话传入的是地址,必须做一次拷贝
            System.out.println(new ArrayList<>(l).toString());
        }else{
            for(int i = 0;i<nums.length;i++){//此步骤是为了看数组中是否有之前用过的数
                if(!used[i]){
                    l.add(nums[i]);
                    used[i]=true;
                    helper(result,l,nums,index+1,used);
                    l.remove(index); //回溯
                    used[i]=false;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] a = {1,2,3};
        List<List<Integer>> permute = permute(a);
    }
}

2.有重复数字
Leetcode47.全排列II:给定一个有重复数字的序列,按任意顺序返回所有不重复的全排列。
此题是对于上题,做了进一步要求,要求序列中有重复数字,单输出得去重,如果用set会耗费大量的资源。
对于全排列中有重复元素如何去重,可以进行剪枝操作。
即先对数组进行排序,然后在回溯时进行一个判断是否要进行剪枝。注意要先排序判断代码如下:

if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){        //剪枝
                continue;
            }

解释一下就是,前一个数没有用过,且当前数与前一个数相等,就进行剪枝,比如[1,1,2],选中第一个1时,就已经排列过[1,1,2],当选中第二个1时,如果没有此判断,第一个1没有用过,会选第一个1,从而得到[1,1,2]重复结果,有判断的话,前面一个1没有用过,并且与前面的1重复,就进行剪枝,排列后面的[1,2,1],总的代码如下:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    List<List<Integer>> res;
    List<Integer> list;
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length==0){
            return new ArrayList<List<Integer>>();
        }
        this.res = new ArrayList<>();
        this.list = new ArrayList<>();
        this.used = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,0);
        return res;
    }

    public void dfs(int[] nums,int index){
        if(index == nums.length){
            res.add(new ArrayList<>(list));
        }
        for (int i = 0; i < nums.length; i++) {
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){        //剪枝
                continue;
            }
            if(!used[i]){
                used[i] = true;
                list.add(nums[i]);
                dfs(nums,index+1);
                used[i] = false;
                list.remove(list.size()-1);
            }
        }
    }
}

二、组合

1.没有重复数字
LeetCode39.总数之和:给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
代码如下:

import java.util.*;

public class Solution {
    List<List<Integer>> res;
    Deque<Integer> de;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.res = new ArrayList<>();
        this.de = new ArrayDeque<>();
        Arrays.sort(candidates);
        dfs(candidates,target,0);
        return  res;
    }
    public void dfs(int[] candidates, int target,int start){
        if(target == 0){
            res.add(new ArrayList<>(de));
        }

        for (int i = start; i < candidates.length; i++) {
            int temp = candidates[i];
            if (target-temp<0){    //排序后,如果当前的值减去temp小于0,即后面的都小于0,直接break
                break;
            }
            de.addLast(temp);
            dfs(candidates,target-temp,i); //因为递归下去仍需要遍历重复元素,但是第二轮就可以直接从i++开始遍历
            de.removeLast();
        }
    }
}

2.有重复数字
LeetCode40.总和之和II:给定一个数组 candidates (数组中的数字可能重复)和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
对于重复的数字,如何去重,代码如下,主要要先进行排序

if(i>index&&candidates[i] == candidates[i-1]){
                    continue;       //剪枝,同一层,当当前的数不是第一个出现且是重复出现的话,
                                    // 就会出现重复元素,就对其进行剪枝
                                    //这样可以避免相同的情况筛选两次(一次原生For循环,一次是递归)
                }

这样可以避免相同的情况筛选两次(一次原生For循环,一次是递归)。
总的代码:

public class Solution {
    private ArrayList<List<Integer>> res;
    private ArrayList<Integer> list;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new ArrayList<>();
        list = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates,target,0);
        return res;
    }

    public void dfs(int[] candidates,int target,int index){
        if(target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        //for循环是平级,递归是往下走
        for (int i = index; i < candidates.length; i++) {
            if(target-candidates[i]>=0){
                if(i>index&&candidates[i] == candidates[i-1]){
                    continue;       //剪枝,同一层,当当前的数不是第一个出现且是重复出现的话,
                                    // 就会出现重复元素,就对其进行剪枝
                                    //这样可以避免相同的情况筛选两次(一次原生For循环,一次是递归)
                }
                list.add(candidates[i]);
                dfs(candidates,target-candidates[i],i+1);
                list.remove(list.size()-1);
            }
        }
    }
}

三、子集

1.没有重复数字
Leetcode78.子集:给定一组不含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)。
代码如下:

public class Solution {
    private ArrayList<List<Integer>> res;
    private ArrayList<Integer> list;
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        list = new ArrayList<>();
        res.add(new ArrayList<>());
        dfs(nums,0);
        return res;

    }
    public void dfs(int[] nums,int index){
        for(int i = index;i<nums.length;i++){
            list.add(nums[i]);
            res.add(new ArrayList<>(list));
            dfs(nums,i+1);
            list.remove(list.size()-1);
        }
    }
}

2.有重复数字
LeetCode90.子集II:给定一个可能包含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)。
去重方法类似于组合,注意要先进行排序,代码如下:

if(i>index&&nums[i]==nums[i-1]){
                continue;
            }

总代码如下:

public class Solution {
    ArrayList<List<Integer>> res = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if(nums.length==0){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        res.add(new ArrayList<>());
        dfs(nums,0);
        return res;
    }

    public void dfs(int[] nums,int index){
        for (int i = index; i < nums.length; i++) {
            if(i>index&&nums[i]==nums[i-1]){
                continue;
            }
            list.add(nums[i]);
            res.add(new ArrayList<>(list));
            dfs(nums,i+1);
            list.remove(list.size()-1);
        }
    }
}

本文地址:https://blog.csdn.net/weixin_44499544/article/details/112299680