算法--回溯算法算法–回溯算法

80 阅读 0 评论 53 点赞

我是靠谱客的博主伶俐棉花糖，最近开发中收集的这篇文章主要介绍算法--回溯算法算法–回溯算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法–回溯算法

排列问题（借用布鲁布鲁吐泡泡）
回溯问题一般常见两种操作是去重和剪枝。
（1）去重是为了避免出现重复的结果。
（2）剪枝是为了当出现明显的不符合题目的要求时，跳过这一元素，节省时间。

组合总数

在这里插入图片描述

class Solution {
     List<List<Integer>> res = new ArrayList<>();
   private  void dfs(int[] candidates,int target,List<Integer> temp,int index)
    {
        if(target==0)
        {
            res.add(new ArrayList<>(temp));
            return ;
        }
        for(int i=index;i<candidates.length;i++){
            if(i!=index&&candidates[i]==candidates[i-1])
            continue;//去重
            if(target<candidates[i])
            break;//剪枝
            temp.add(candidates[i]);
            dfs(candidates,target-candidates[i],temp,i+1);
            temp.remove(temp.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,new ArrayList<>(),0);
        return res;
    }
}

为了方便处理重复问题，首先对数组进行排序。确保重复的数组元素相邻。

 Arrays.sort(candidates);

在回溯函数中，进行去重操作。

 if(i!=index&&candidates[i]==candidates[i-1])
            continue;

index代表当前层

四数之和

在这里插入图片描述

class Solution {
    List<List<Integer>> res = new ArrayList();
    boolean []vis;
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        vis = new boolean[nums.length];
        backTracking(nums,new ArrayList<Integer>(),target,vis,0);
        return res;
    }
    private void backTracking(int[] nums,List<Integer> temp,int target,boolean[] vis,int index){
        if(temp.size()==4&&target==0){
            res.add(new ArrayList<>(temp));
            return;
        }
        else if(temp.size()==4){
            return;
        }

        for(int i=index;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&!vis[i-1]){//去重
                continue;
            }
            if(temp.size()==3&&target-nums[i]!=0){//剪枝条(节省时间)
                continue;
            }
            temp.add(nums[i]);
            vis[i] = true;
            backTracking(nums,temp,target-nums[i],vis,i+1);
            vis[i] = false;
            temp.remove(temp.size()-1);
        }
    }
}

与上一个问题组合总数类似，都是组合数字求和问题，不同点在于四数之和限制了结果的个数只能是4个数字之和。
新增添了一个布尔型数组vis来判断当前元素是否被访问过。去重操作如下：

if(i>0&&nums[i]==nums[i-1]&&!vis[i-1]){//去重
                continue;
            }

nums[i]==nums[i-1]&&vis[i-1]==false,代表当前元素与之前一个元素相等，且前一个元素本次回溯未被访问。

全排列II

在这里插入图片描述

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    boolean []vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        vis = new boolean[nums.length];
        backTracking(nums,new ArrayList<>(),0,vis);
        return res;
    }
    private void backTracking(int[] nums,List<Integer> temp,int index,boolean[] vis){
        if(temp.size()==nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        
        for(int i=0;i<nums.length;i++){
           
            if(vis[i]||(i>0&&nums[i]==nums[i-1]&&!vis[i-1])){
                continue;
            }
            temp.add(nums[i]);
            vis[i] = true;
            backTracking(nums,temp,index+1,vis);
            temp.remove(temp.size()-1);
            vis[i] = false;
        }
    }

}