Leetcode 组合总和问题

文章目录

39.组合总和

题目设定:

给的数组没有重复元素,同一个元素可以无限引用,最后的结果不能重复

树形图如下:

Leetcode 组合总和问题
因为没有重复元素,不用考虑去重的问题

元素可以重复使用,所以递归的时候需要从 i 往下,而不是i+1

对一个数组且元素相关,需要startindex

故代码如下:

class Solution {
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    private LinkedList<Integer> path = new LinkedList<Integer>(); 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates,target,0,0);
        return ans;
    }
    public void backtrack(int[] candidates,int target,int sum,int startIndex){
        if(sum>target) return;
        if(sum == target){
            ans.add(new ArrayList<> (path));
            return;
        }
        for(int i = startIndex;i<candidates.length;i++){
            sum+=candidates[i];
            path.add(candidates[i]);
            backtrack(candidates,target,sum,i);
            sum-=candidates[i];
            path.removeLast();
        }
        
    }
}

剪枝操作:

只需判断sum+candidates[i]<=target即可

但注意,剪枝需要先排序

剪枝后代码:

class Solution {
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    private LinkedList<Integer> path = new LinkedList<Integer>(); 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates,target,0,0);
        return ans;
    }
    public void backtrack(int[] candidates,int target,int sum,int startIndex){
        if(sum>target) return;
        if(sum == target){
            ans.add(new ArrayList<> (path));
            return;
        }
        for(int i = startIndex;i<candidates.length && sum+candidates[i]<=target;i++){
            sum+=candidates[i];
            path.add(candidates[i]);
            backtrack(candidates,target,sum,i);
            sum-=candidates[i];
            path.removeLast();
        }
        
    }
}

40.组合总和Ⅱ

题目设定:

给的集合有重复元素,每个元素只能用一次最后不能有重复集合

树形图:
Leetcode 组合总和问题

注意:
有重复元素,就需要去重
去重方法:创建一个boolean[] used 数组,通过一下代码去重

if(i>0 && candidates[i]==candidates[i-1] && !used[i-1])
            continue;

只能用一次,递归的时候应该是 i+1 ,而不是 i

剪枝的操作同上

代码如下:

class Solution {
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    private LinkedList<Integer> path = new LinkedList<Integer>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backtrack(candidates,target,0,0,used);
        return ans;
    }
    public void backtrack(int[] candidates, int target,int startIndex,int sum,boolean[] used){
        if(sum>target) return;
        if(sum == target){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex;i<candidates.length && sum+candidates[i]<=target;i++){
            if(i>0 && candidates[i]==candidates[i-1] && !used[i-1])
            continue;
            used[i] = true;
            path.add(candidates[i]);
            sum += candidates[i];
            backtrack(candidates,target,i+1,sum,used);
            sum -= candidates[i];
            path.removeLast();
            used[i] = false;
        }
        
    }
}

组合总和Ⅲ

题目设定:
找到n个数 和为k 只能有1-9数组且不能有重复数字

树形图:
Leetcode 组合总和问题
没有重复数字,只有1-9,即不用去重

数字只能有一个,递归则为 i+1

即先要找k个数字,再判断其和,如果为target,加入ans,如果不是,两种情况一起return到上一层

class Solution {
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    private LinkedList<Integer> path = new LinkedList<Integer>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k,n,1,0);
        return ans;
    }
    public void backtrack(int k,int n,int startindex,int sum){
        if(path.size() == k){
            if(sum == n)
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i = startindex;i<=9;i++){
            sum += i;
            path.add(i);
            backtrack(k,n,i+1,sum);
            path.removeLast();
            sum -= i;
        }
    }
}

组合总和Ⅳ

题目设定:
数组元素没有重复的,元素可以无限使用,但是结果可以重复,顺序不同即可

这题我用回溯,超时了

用动态规划,用爬楼梯的思想

target为要上的楼梯的层数,nums[ ]为一次能上的层数

代码:

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 1;i<=target;i++){
            for(int j = 0;j<nums.length;j++){
                if(i-nums[j]>=0) dp[i] += dp[i-nums[j]];
            }
        }
        return dp[target];
    }
}
上一篇:【LeetCode】3. 无重复字符的最长子串


下一篇:【LeetCode】438. 找到字符串中所有字母异位词