Java描述 LeetCode，216. Combination Sum III 组合总和 III

Java描述 LeetCode，216. Combination Sum III 组合总和 III

푰’풎 풉풉품, 푰 풂풎 풂 품풓풂풅풖풂풕풆 풔풕풖풅풆풏풕 풇풓풐풎 푵풂풏풋풊풏품, 푪풉풊풏풂.

 푺풉풄풐풐풍: 푯풐풉풂풊 푼풏풊풗풆풓풔풊풕풚 푳풆풂풓풏풊풏품: 푰’풎 풄풖풓풓풆풏풕풍풚 풍풆풂풓풏풊풏품 풅풆풔풊품풏 풑풂풕풕풆풓풏, 푳풆풆풕풄풐풅풆, 풅풊풔풕풓풊풃풖풕풆풅 풔풚풔풕풆풎, 풎풊풅풅풍풆풘풂풓풆 풂풏풅 풔풐 풐풏. 푯풐풘 풕풐 풓풆풂풄풉 풎풆：푽푿 푴풚 풃풍풐품: 풉풕풕풑풔://풉풉품풚풚풅풔.풃풍풐품.풄풔풅풏.풏풆풕/ 푷풓풐풇풆풔풔풊풐풏풂풍 풔풌풊풍풍풔：풎풚 풅풓풆풂풎
1-1：Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

2 <= k <= 9
1 <= n <= 60

通过次数120,523提交次数164,156

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1-2：Two Backtracking Solutions

方法一：Java描述 LeetCode，77. Combinations 组合，和这道题目的思路完全一致，只不过这里要加入额外的一个限制条件，那就是总和sum，在剪枝的时候可以多一些剪枝手段。代码如下：

private linkedList path;
private List> result = new ArrayList<>();

public List> combinationSum3(int k, int n) {
    this.path = new linkedList<>();
    dfs(k, n, 1, 9);
    return result;
}

// begin代表[begin..9]，代表待选数字的开始
// sum是总和里剔除了所选值之后的数字，比如 [1..9]选3个数使sum=9，选了1，sum=9-1，还余8继续选
public void dfs(int k, int sum, int begin, int n) {
    // 1. 选够了k个数，并且这k个数的和是sum就是我们想要的目标，我们这里是挨个选的，比如[1..9] 选3个数 和= 9，那么就有[1,2,3]的这种情况，这种情况就不是我们要的。
    if (sum == 0 && path.size() == k) {
        // 2. 不能直接add path，后续 *** 作会修改path的值，会影响前面的结果，和Java的语法有关
        result.add(new ArrayList<>(path));
        return;
    }
    // 3. n-i+1是待选的数>=选k-path.size()个数字，比如[8,9]一共剩2个要选3个数不可能的，并且剩余值sum>i的值才能选，比如[i=4..9]选sum=3就没有必要
    for (int i = begin; i <= sum && k - path.size() <= n - i + 1; i++) {
        path.addLast(i);
        dfs(k, sum - i, i + 1, n);
        // 4. 回退，理由T77里面已经有了
        path.removeLast();
    }
}

注释足够详细。

方法二：

public List> combinationSum3_2(int k, int n) {
    this.path = new linkedList<>();
    dfs2(k, n, 1, 9);
    return result;
}

public void dfs2(int k, int sum, int begin, int n) {
    if (sum == 0 && path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 剪枝，这里是||的条件，不是&&，这个问题坑了我很久zz
    if (sum < begin || n - begin + 1 < k - path.size()) {
        return;
    }
    dfs2(k, sum, begin + 1, n);
    path.addLast(begin);
    dfs2(k, sum - begin, begin + 1, n);
    path.removeLast();
}

和方法一差不多，关键是剪枝的条件。核心思路就是T77里面的。

我总感觉最后一个数字的时候也可以剪枝，和确定了，选了k-1个数字，那么最后一个数字不就是num - k1,-k2-…- kn-1？但是我比较笨，没有实现，你觉得呢？