资讯专栏INFORMATION COLUMN

[Leetcode] Combination Sum 组合数之和

GitCafe / 2610人阅读

摘要:深度优先搜索复杂度时间空间递归栈空间思路因为我们可以任意组合任意多个数,看其和是否是目标数,而且还要返回所有可能的组合,所以我们必须遍历所有可能性才能求解。这题是非常基本且典型的深度优先搜索并返回路径的题。本质上是有限深度优先搜索。

Combination Sum I

Given a set of candidate numbers (C) 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.

Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7, A solution set is:

[7] 
[2, 2, 3]
深度优先搜索 复杂度

时间 O(N!) 空间 O(N) 递归栈空间

思路

因为我们可以任意组合任意多个数,看其和是否是目标数,而且还要返回所有可能的组合,所以我们必须遍历所有可能性才能求解。为了避免重复遍历,我们搜索的时候只搜索当前或之后的数,而不再搜索前面的数。因为我们先将较小的数计算完,所以到较大的数时我们就不用再考虑有较小的数的情况了。这题是非常基本且典型的深度优先搜索并返回路径的题。本题需要先排序,不然过不了Leetcode。

注意

要先问清楚什么样的组合是有效的,比如该题,是可以连续选择同一个数加入组合的。

代码
public class Solution {
    
    List> res;
    
    public List> combinationSum(int[] candidates, int target) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        // 先将数组排序避免重复搜素
        Arrays.sort(candidates);
        helper(candidates, target, 0, tmp);
        return res;
    }
    
    private void helper(int[] nums, int target, int index, List tmp){
        // 如果当前和已经大于目标,说明该路径错误 
        if(target < 0){
            return;
        // 如果当前和等于目标,说明这是一条正确路径,记录该路径
        } else if(target == 0){
            List oneComb = new LinkedList(tmp);
            res.add(oneComb);
        // 否则,对剩余所有可能性进行深度优先搜索
        } else {
            // 选取之后的每个数字都是一种可能性
            for(int i = index; i < nums.length; i++){
                // 典型的先加入元素,再进行搜索,递归回来再移出元素的DFS解法 
                tmp.add(nums[i]);
                helper(nums, target - nums[i], i, tmp);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}
Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note: All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending
order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain
duplicate combinations. For example, given candidate set
10,1,2,7,6,1,5 and target 8, A solution set is:

[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6]
深度优先搜索 复杂度

时间 O(N!) 空间 O(N) 递归栈空间

思路

这题和I的区别在于同一个数只能取一次,比如数组中只有3个1,那结果中也最多只有3个1,而且结果也不能重复。所以我们在递归时首先要把下标加1,这样下轮搜索中就排除了自己。其次,对一个数完成了全部深度优先搜索后,比如对1完成了搜索,那么我们要把后面的1都跳过去。当然,跳过只是针对本轮搜索的,在对第一个1的下一轮的搜索中,我们还是可以加上第二个1。只是我们不能再以第二个1开头了而已。为了能连续跳过重复的数,这里我们必须先排序。

代码
public class Solution {
    
    List> res;
    
    public List> combinationSum2(int[] candidates, int target) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        Arrays.sort(candidates);
        helper(candidates, target, 0, tmp);
        return res;
    }
    
    private void helper(int[] nums, int target, int index, List tmp){
        if(target < 0){
            return;
        } else if(target == 0){
            List oneComb = new LinkedList(tmp);
            res.add(oneComb);
        } else {
            for(int i = index; i < nums.length; i++){
                tmp.add(nums[i]);
                // 递归时下标加1
                helper(nums, target - nums[i], i+1, tmp);
                tmp.remove(tmp.size() - 1);
                // 跳过本轮剩余的重复元素
                while(i < nums.length - 1 && nums[i] == nums[i + 1]){
                    i++;
                }
            }
        }
    }
}
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.

Ensure that numbers within the set are sorted in ascending order.

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]]
深度优先搜索 复杂度

时间 O(9!) 空间 O(9) 递归栈空间

思路

这题其实是II的简化版,设想一个[1,2,3,4,5,6,7,8,9]的数组,同样一个元素只能取一次,但是已经预先确定没有重复了。所以可以省去跳过重复元素的部分。不过,我们在递归的时候要加一个额外的变量k来控制递归的深度,一旦超过了预设深度,就停止该分支的搜索。本质上是有限深度优先搜索。

代码
public class Solution {
    
    List> res;
    
    public List> combinationSum3(int k, int n) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        helper(k, n, 1, tmp);
        return res;
    }
    
    private void helper(int k, int target, int i, List tmp){
        if(target < 0 || k < 0){
            return;
        } else if (target == 0 && k == 0){
            List oneComb = new LinkedList(tmp);
            res.add(oneComb);
        } else {
            for(int j = i; j <= 9; j++){
                tmp.add(j);
                helper(k-1, target-j, j+1, tmp);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}

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

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

相关文章

  • [LintCode/LeetCode] Combination Sum I & II

    摘要:和唯一的不同是组合中不能存在重复的元素,因此,在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

    ThreeWords 评论0 收藏0
  • LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)

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

    linkin 评论0 收藏0
  • leetcode216. Combination Sum III

    摘要:题目要求输入和,找到所有个不同数字的组合,这些组合中数字的和为参考,解答这是一道典型的的题目,通过递归的方式记录尝试的节点,如果成功则加入结果集,如果失败则返回上一个尝试的节点进行下一种尝试。 题目要求 Find all possible combinations of k numbers that add up to a number n, given that only numbe...

    awokezhou 评论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
  • leetcode 40 Combination Sum II

    摘要:要求中的每一个元素在一个组合中只能被使用一次。输入候选数字集和目标数字结果集应当是想法首先这道题和题非常的相像。因此和题的解法相比,我们需要进行一次对于重复元素跳过的操作。 题目详情 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C...

    li21 评论0 收藏0

发表评论

0条评论

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