[LeetCode] Combination Sum III | Combination Sum I

leiyi 發布于2019-08-14 15:48 / 1331人閱讀

摘要：此時，若也正好減小為，說明當前集合是正解，加入數組。兩個無法得到正解的情況是在為，而不為時，當然已經無法得到正解，。在不為而卻已經小于等于的情況下，此時仍要加入其它數以令為，而要加入的數都是到的正整數，所以已無法滿足令為的條件，。

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]);
        }
    }
}

GPU云服務器云服務器 Combination sum hibernate 分頁 sum three-sum

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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