[LintCode/LeetCode] Combination Sum I & II

ThreeWords 發布于2019-08-14 15:23 / 2839人閱讀

摘要：和唯一的不同是組合中不能存在重復的元素，因此，在遞歸時將初始位即可。

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.

The same repeated number may be chosen from C unlimited number of times.

Notice

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.

Example

given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Note

基本思路與Combinations一致，遞歸模板詳見：https://segmentfault.com/a/11...
有兩個點需要注意：在組合中的數必須是升序排列，所以在調用dfs函數之前要先排序；另外，由于組合里允許有重復數，dfs調用自身時，初始位start(=i)的位置不變，依然從i開始，只需將target減小num[i]即可。

Solution Recursion 26ms

public class Solution {
    List> res = new ArrayList<>();
    public List> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        helper(candidates, 0, target, new ArrayList());
        return res;
    }
    public void helper(int[] c, int start, int t, List pre) {
        if (t < 0) return;
        if (t == 0) res.add(pre);
        for (int i = start; i < c.length; i++) {
            List cur = new ArrayList(pre);
            cur.add(c[i]);
            helper(c, i, t-c[i], cur);
        }
    }
}

Combination Sum II Problem

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.

Notice

Example

Given candidate set [10,1,6,7,2,1,5] and target 8,

A solution set is:

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

Note

和Combination Sum I唯一的不同是組合中不能存在重復的元素，因此，在dfs遞歸時將初始位+1即可。

Solution

public class Solution {
    List> res = new ArrayList>();
    public List> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        helper(num, 0, target, new ArrayList());
        return res;
    }
    public void helper(int[] num, int start, int target, List pre) {
        if (target < 0) return;
        if (target == 0) {
            res.add(pre);
            return;
        }
        for (int i = start; i < num.length; i++) {
            if (i > start && num[i] == num[i-1]) continue;
            List cur = new ArrayList (pre);
            cur.add(num[i]);
            helper(num, i+1, target-num[i], cur);
        }
    }
}

Combination Sum III & IV link: here

云服務器 GPU云服務器 II ii6 ii7 Combination

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65721.html

[LintCode/LeetCode] Subsets &amp; Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 評論0 收藏0
[LintCode/LeetCode] Single Number I &amp; II [位運算]

摘要：整個過程相當于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現過一次的，而出現兩次的都在里，出現三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 評論0 收藏0
[LintCode/LeetCode] Jump Game I &amp; II

摘要：建立動規數組，表示從起點處到達該點的可能性。循環結束后，數組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數。此時的一定是滿足條件的最小的，所以一定是最優解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 評論0 收藏0
[LintCode/LeetCode] Unique Paths II

摘要：和完全一樣的做法，只要在初始化首行和首列遇到時置零且即可。對了，數組其它元素遇到也要置零喏，不過就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...

firim 2019-08-14 15:29 評論0 收藏0
[LintCode/LeetCode] Contains Duplicate II

Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...

894974231 2019-08-19 10:48 評論0 收藏0