资讯专栏INFORMATION COLUMN

Leet code -- Combination Sum系列整理

hankkin / 2408人阅读

摘要:给定一个正整数数组元素无重复,给定目标,找出组合的个数,使得组合中元素的和等于。数组元素可以重复使用递归调用循环中,对于第一题修改的起始位置即可但是。结果如果第一处修改成结果变为如果第一处修改为以及第二处修改为结果变为

Combination Sum I

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
例如: [2, 3, 6, 7] and target 7

[
  [7],
  [2, 2, 3]
]

给定一个数组(元素无重复),和一个目标值,找到所有组合,加起来等于目标值。数组中的元素可以重复使用.
解法:

public class CombinationSum {
    public static List> combinationSum(int[] candidates, int target){
        Arrays.sort(candidates);
        List> result = new ArrayList<>();
        getResult(result, new ArrayList(), candidates, target, 0);
        return result;
    }

    private static void getResult(List> result, ArrayList current, int[] candidates, int target,
            int start) {
        if(target<0)    return;
        if(target==0){
            result.add(new ArrayList<>(current));
            return;
        }
        for(int i = start; i= candidates[i]; i++){
            current.add(candidates[i]);
            getResult(result, current, candidates, target-candidates[i], i);
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {2,3,6,7};
        System.out.println(combinationSum(nums, 7));
    }
}
LC40. Combination Sum II

给定一个数组(元素可以有重复),和一个目标值,找到所有组合,加起来等于目标值。数组中的元素不能重复使用。
例子: [10, 1, 2, 7, 6, 1, 5] and target 8

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

解法:

/**
 * 要去重,注意边界,递归时候要加一
 */
public class CombinationSum2 {
    public List> combinationSum2(int[] candidates, int target) {
        List> result = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(result, new ArrayList(), candidates, target, 0);
        return result;
    }
    
    private void dfs(List> result, ArrayList current, int[] candidates, int target, int start) {
        if(target < 0)  return;
        if(target == 0){
            result.add(new ArrayList(current));
            return;
        }
        for(int i = start; i= candidates[i]; i++){
            current.add(candidates[i]);
            dfs(result, current, candidates, target - candidates[i], i+1);    // 此处注意i+1,每个元素只能用一次,加一后在向下递归
            current.remove(current.size()-1);
            while(i < candidates.length - 1 && candidates[i] == candidates[i+1]) i++;    // 去重复(注意上面有i+1,这里要length-1,边界问题)
        }
    }
    public static void main(String[] args) {
        int[] array = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        System.out.println(new CombinationSum2().combinationSum2(array, target));
    }
}
LC216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1: Input: k = 3, n = 7

Output: [[1,2,4]]

Example 2: Input: k = 3, n = 9

Output: [[1,2,6], [1,3,5], [2,3,4]]

给定K和N,从1--9中这几个9个数字组合出来K个数,其和为N。1-9不能重复使用.

/**
 * 注意结束条件:size达到k值 并且 剩余值为0
 */
public class CombinationSum3 {
    public List> combinationSum3(int k, int n) {
        List> result = new ArrayList<>();
        dfs(result, new ArrayList(), k, n, 1);
        return result;
    }
    private void dfs(List> result, ArrayList current, int k, int remainder, int start){
        if(current.size() == k && remainder == 0){ //size达到k值 并且 剩余值为0
            result.add(new ArrayList<>(current));
            return ;
        }
        for(int i = start; i<=9 && remainder >= i; i++){
            current.add(i);
            dfs(result, current, k, remainder - i, i+1); // 不重复,i+1
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        System.out.println(new CombinationSum3().combinationSum3(3, 15));
    }
}
LC 377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example: nums = [1, 2, 3], target = 4

The possible combination ways are:

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.
Therefore the output is 7.

Follow up: What if negative numbers are allowed in the given array?
How does it change the problem? What limitation we need to add to the
question to allow negative numbers?

如果有负数,就不能让数组中的元素重复使用。

给定一个正整数数组(元素无重复),给定目标target,找出组合的个数,使得组合中元素的和等于target。数组元素可以重复使用.

public class CombinationSum4 {
    public int combinationSum4(int[] candidates, int target){
        List> result = new ArrayList<>();
        dfs(result, new ArrayList(), candidates, target, 0);
        return result.size();
    }
    
    private void dfs(List> result, ArrayList current, int[] candidates, int target, int start) {
        if(target < 0)    return;
        if(target == 0){
            result.add(new ArrayList<>(current));
            return;
        }
        for(int i = 0; i= candidates[i]; i++){
            current.add(candidates[i]);
            dfs(result, current, candidates, target-candidates[i], i);
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        System.out.println(new CombinationSum4().combinationSum4(arr, 4));
    }
}

递归调用循环中,对于第一题修改i的起始位置即可:i = 0
但是TLE。递归深度太深。
所以这个方法是不行的。
需要使用DP。

public int combinationSum4(int[] candidates, int target){
    Arrays.sort(candidates);
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for(int i = 1; i i)    break;
            dp[i] += dp[i - curr];
        }
    }
    return dp[target];
}
面试题:修改版

有道面经题目是一个修改版,也是返回组合个数即可,但是加了条件:去掉重复。
上面的例子:nums = [1, 2, 3] target = 4 ,返回 7.
The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
这个题目要返回的是4,所有的组合是:(1, 1, 1, 1) (1, 1, 2) (1, 3) (2, 2) (3, 1)
变成第一题了:需要改变返回值,返回大小即可。

看一下这几个的区别,轻微的改动,产生的不同结果:
以第一题Combination Sum I为基础:

public class CombinationSum {
    public static List> combinationSum(int[] candidates, int target){
        Arrays.sort(candidates);
        List> result = new ArrayList<>();
        getResult(result, new ArrayList(), candidates, target, 0);
        return result;
    }
    
    private static void getResult(List> result, ArrayList current, int[] candidates, int target,
            int start) {
        if(target < 0)    return; // 是有可能小于0的
        if(target == 0){
            result.add(new ArrayList<>(current)); // 此处注意
            return;
        }
        // 注意点1
        for(int i = start; i= candidates[i]; i++){
            current.add(candidates[i]);
            getResult(result, current, candidates, target-candidates[i], i); // 注意点2
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(combinationSum(nums, 4));
    }
}

在上面的两个注意点上:
第一题:数组(元素无重复),数组中的元素可以重复使用。结果

[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2]]

如果第一处修改成 i = 0 结果变为:

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]

如果第一处修改为 i = start 以及 第二处修改为 i+1 结果变为:

[[1, 3]]

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66761.html

相关文章

  • LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列

    摘要:输入输出分析题目由于我们需要找到多个组合,简单的使用循环肯定是不行的,这时候我们可以使用回溯算法来解决这个问题。用回溯算法解决问题的一般步骤针对所给问题,定义问题的解空间,它至少包含问题的一个最优解。 题目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...

    linkin 评论0 收藏0
  • leetcode 部分解答索引(持续更新~)

    摘要:前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写~现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。 顺序整理 1~50 1...

    leo108 评论0 收藏0
  • [LeetCode] Combination Sum III | Combination Sum I

    摘要:此时,若也正好减小为,说明当前集合是正解,加入数组。两个无法得到正解的情况是在为,而不为时,当然已经无法得到正解,。在不为而却已经小于等于的情况下,此时仍要加入其它数以令为,而要加入的数都是到的正整数,所以已无法满足令为的条件,。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...

    leiyi 评论0 收藏0
  • 整理了一周的Python资料,包含各阶段所需网站、项目,收藏了慢慢来

    摘要:希望能够帮助到大家,减少在起步阶段的油耗,集中精神突破技术。关注公众后,后台回复关键字资料,获取项目包本篇文章对不同阶段的人群都适用,别再说怎么学,没有实战项目了。 showImg(https://segmentfault.com/img/bVbpcg3?w=1318&h=730); 这周应该有不少学校已经开学了,那么同学们都该动起来了,把家里面的那些懒习惯给扔掉了可以。 不知怎么的,...

    liuhh 评论0 收藏0

发表评论

0条评论

hankkin

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<