回溯算法复习

Posted by DeepBlue on 12-05,2020

回溯算法复习

题目来源:力扣

39. 组合总和

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入:candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

因为题目中每个数字可以重复使用多次,那么我们就可以画出如下的图,利用回溯算法进行选择,开始写代码。

排序后进行剪枝更加的高效,首先上图中,因为每个数字都要被重复的使用,那么例如[1,3,9,5,2]中,我们如果不进行排序,那么只有在

解题代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length==0){
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        //排序后进行剪枝更加的高效
        Arrays.sort(candidates);
        dfs(candidates,0,target,new ArrayDeque<Integer>(),result);
        return result;
    }
    public void dfs(int[] candidates,int begin,int target,Deque<Integer> path,List<List<Integer>> result){
        if(target==0){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        //为什么从begin开始?,因为我们的数组是无重复的,那么数组如果已经进行到了第i个元素,
        //那么0到(i-1)中的每个结果都被包括在结集中,所以不用进行重复的考虑
        for(int i=begin;i<candidates.length;i++){
            if(target-candidates[i]<0){
                break;
            }
            path.addLast(candidates[i]);
            dfs(candidates,i,target-candidates[i],path,result);
            path.removeLast();
        }

    }
}

40. 组合总和 II

题目描述

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明

所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

此题与上题组合总和不同点在于,本题目中的数组中的元素只能使用一次,那么我们就要考虑如何去重重复:先对数组 升序 排序,重复的元素一定不是排好序以后相同的连续数组区域的第 1 个元素。也就是说,剪枝发生在:同一层数值相同的结点第 2、3 ... 个结点,因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果。那么我们就可以使用语句

for(int i=begin;i<candidates.length;i++){
	if(candidates[i]==candidates[i-1]){
    	continue;
    //do somethng!
    }

进行剪枝

作者:liweiwei1419
链接:https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

解题代码

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates.length==0){
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        dfs(candidates,target,new ArrayDeque<Integer>(),result,0);
        return result;
    }
    public void dfs(int[] candidates, int target,Deque<Integer> path,List<List<Integer>> result,int begin){
        if(target==0){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=begin;i<candidates.length;i++){
            if(target-candidates[i]<0){
                break;
            }
            //解释一下这句话,i>begin保证了两个相同的数不会出现在同一层级
            //candidates[i]==candidates[i-1]保证了同一层不会出现重复元素的
            if(i>begin&&candidates[i]==candidates[i-1]){
                continue;
            }
            path.addLast(candidates[i]);
            dfs(candidates,target-candidates[i],path,result,i+1);
            path.removeLast();
        }
    }
}

216. 组合总和 III

题目描述

找出所有相加之和为 nk 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

思想和上面一样,不再赘述了。

解题代码

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        dfs(k,n,result,1,new ArrayDeque<Integer>());
        return result;
    }
    public void dfs(int k, int n,List<List<Integer>> result,int begin,Deque<Integer> path){
        if(path.size()==k&&n==0){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        if(path.size()>k||n<0){
            return;
        }
        for(int i=begin;i<=9;i++){
            if(n-i<0){
                break;
            }
            path.add(i);
            dfs(k,n-i,result,i+1,path);
            path.removeLast();
        }
    }
}

46. 全排列

题目描述

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

示例:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

回溯法,和上面一样,思路的话,组成和途中一样的树,不过判断条件不同,是将

解题代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(nums==null){
            return result;
        }
        dfs(nums,result,new ArrayDeque<Integer>(),new boolean[nums.length]);
        return result;
    }

    public void dfs(int[] nums,List<List<Integer>> result,Deque<Integer> path,boolean[] used){
        if(path.size()==nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            dfs(nums,result,path,used);
            used[i]=false;
            path.removeLast();
        }
    }
}

47. 全排列 II

题目描述

给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

思路和组合中的二一样,只不过是判断条件略有不同,且其中判断重复的语句略有不同。

解题代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        ArrayDeque<Integer> deque=new ArrayDeque<Integer>();
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        dfs(nums,deque,new boolean[nums.length],result);
        return result;
    }
    public void dfs(int[] nums,Deque<Integer> path,boolean[] used,List<List<Integer>> result){
        if(path.size()==nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            //剪枝的过程中去重。
            //i>0&&nums[i-1]==nums[i]防止同一层出现重复,但是同一路径下的重复是被允许的。
            if(i>0&&nums[i-1]==nums[i]&&!used[i-1]){
                continue;
            }
            used[i]=true;
            path.addLast(nums[i]);
            dfs(nums,path,used,result);
            used[i]=false;
            path.removeLast();
        }
    }
}

78. 子集

题目描述

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

**说明:**解集不能包含重复的子集。

示例

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

这道题同样也是用了回溯算法,和上面的组合一样,我们可以将其拆分成从0到length-1长度的数组求其组合,最后得到的答案就是本题的答案。

解题代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        for(int i=0;i<=nums.length;i++){
            dfs(nums,i,new ArrayList<Integer>(),result,0);
        }
        return result;
    }

    public void dfs(int[]nums,int count,ArrayList<Integer> path,List<List<Integer>> result,int begin){
        if(path.size() == count){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        if(path.size() > count){
            return;
        }
        for(int i=begin;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,count,path,result,i+1);
            path.remove((int)path.size()-1);
        }
    }
}