[LeetCode] Combination Sum III | Combination Sum I

leiyi 发布于2019-08-14 15:48 / 1276人阅读

摘要：此时，若也正好减小为，说明当前集合是正解，加入数组。两个无法得到正解的情况是在为，而不为时，当然已经无法得到正解，。在不为而却已经小于等于的情况下，此时仍要加入其它数以令为，而要加入的数都是到的正整数，所以已无法满足令为的条件，。

Combination Sum I & II: link

Combination Sum III Problem

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]]

Note

思路和Combination Sum II一样，用DFS递归求解。
加一个参数count = k，count每当有新的数i加入计算集合cur则减一；同时，target，也就是给定的n，也要减少i。
当count为0时，集合里就有k个数了。此时，若target也正好减小为0，说明当前集合pre是正解，pre加入res数组。

两个无法得到正解的情况是：
在count为0，而target不为0时，当然已经无法得到正解，return。
在count不为0而target却已经小于等于0的情况下，此时仍要加入其它数以令count为0，而要加入的数都是1到9的正整数，所以已无法满足令target为0的条件，return。

Solution

public class Solution {
    List> res = new ArrayList<>();
    public List> combinationSum3(int k, int n) {
        helper(1, k, n, new ArrayList());
        return res;
    }
    public void helper(int start, int count, int target, List pre) {
        if (count == 0) {
            if (target == 0) res.add(pre);
            else return;
        }
        else {
            if (target <= 0) return;
            if (target > 0) {
                for (int i = start; i <= 9; i++) {
                    List cur = new ArrayList (pre);
                    cur.add(i);
                    helper(i+1, count-1, target-i, cur);
                }
            }
        }
    }
}

Combination Sum IV Problem:

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?

Solution

DP method

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] dp = new int[target+1];
        for (int i = 1; i <= target; i++) {
            for (int num: nums) {
                if (num == i) dp[i]++;
                else if (num < i) dp[i] += dp[i-num];
                else break;
            }
        }
        return dp[target];
    }
}

Optimized DP

public class Solution {
    public int backPackVI(int[] nums, int target) {
        int[] dp = new int[target+1];
        Arrays.sort(nums);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num: nums) {
                if (num <= i) dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }
}

Another DP

public class Solution {
    public int backPackVI(int[] nums, int target) {
        int[] dp = new int[target+1];
        Arrays.fill(dp, -1);
        Arrays.sort(nums);
        return helper(nums, dp, target);
    }
    
    int helper(int[] nums, int[] dp, int target){
        if (dp[target] >= 0) return dp[target];
        dp[target] = 0;
        for (int i = 0; i < nums.length; i++){
            if (target > nums[i]) dp[target] += helper(nums, dp, target-nums[i]);
            else if (target == nums[i]) {
                dp[target]++;
                break;
            }
        }
        return dp[target];
    }
}

DFS: Exceeded time limit

public class Solution {
    int count = 0;
    public int backPackVI(int[] nums, int target) {
        //int count = 0;
        int sum = 0;
        dfs(nums, target, sum);
        return count;
    }
    
    void dfs(int[] nums, int target, int sum){
        if (sum > target) return;
        else if (sum == target) {
            count++;
        }
        for (int i = 0; i < nums.length; i++) {
            dfs(nums, target, sum+nums[i]);
        }
    }
}

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

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

leetcode216. Combination Sum III

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

awokezhou 2019-08-15 10:57 评论0 收藏0
[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 2019-08-14 15:23 评论0 收藏0
[Leetcode] Combination Sum 组合数之和

摘要：深度优先搜索复杂度时间空间递归栈空间思路因为我们可以任意组合任意多个数，看其和是否是目标数，而且还要返回所有可能的组合，所以我们必须遍历所有可能性才能求解。这题是非常基本且典型的深度优先搜索并返回路径的题。本质上是有限深度优先搜索。 Combination Sum I Given a set of candidate numbers (C) and a target number (...

GitCafe 2019-08-14 12:31 评论0 收藏0
Leetcode 相似题只有题号不含代码。

找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 评论0 收藏0
leetcode40 combination sum 2

摘要：参考思路和非常类似，只是这里需要增加进行重复处理的部分。题目要求题目中新添的要求包括数组中存在重复值，而且数组中每个值只可以使用一次。需要注意的是，既然数组中存在重复的值，就要注意可能会将重复的情况加入结果数组。参考思路和leetcode39 combination sum 非常类似，只是这里需要增加进行重复处理的部分。请参考我对leetcode39进行解答的这篇博客。题目要求 ...

Code4App 2019-08-16 10:33 评论0 收藏0