Leetcode/java/216.combination-sum-iii.java at master · widmonstertony/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.awt.List;
import java.util.ArrayList;

/*
 * @lc app=leetcode id=216 lang=java
 *
 * [216] Combination Sum III
 */

// @lc code=start
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> resList = new ArrayList<>();
        helper(resList, new ArrayList<>(), k, n, 1);
        return resList;
    }
    private void helper(List<List<Integer>> resList, List<Integer> currList, int k, int n, int startNum) {
        if (k == 0 && n == 0) {
            resList.add(new ArrayList<>(currList));
            return;
        }
        // 题目要求1到9，所以最大尝试的数是不超过9
        int tryMax = n;
        if (tryMax > 9) {
            tryMax = 9;
        }
        // 从指定开始数到能尝试的最大数，都试一遍
        for (int i = startNum; i <= tryMax; i++) {
            currList.add(i);
            // 确保startNum从当前位数的后一位开始，消除重复
            helper(resList, currList, k - 1, n - i, i + 1);
            currList.remove(currList.size() - 1);
        }
    }
}
// @lc code=end