0216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii

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.

Example 4:

**Input:** k = 3, n = 2
**Output:** []
**Explanation:** There are no valid combinations.

Example 5:

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

Constraints:

• 2 <= k <= 9

• 1 <= n <= 60

ac

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        // DFS, backtracking
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        // edge cases
        if (k < 1 || n < 1) return res;

        // DFS
        backtrack(1, k, n, new ArrayList<Integer>(), res);

        return res;
    }

    private void backtrack(int s, int k, int remain, List<Integer> note, List<List<Integer>> res) {
        // walk, s <= i <= 9
        // if k == 1, stop, check remain. if remain == 0, add. remain < 0 continue, >0 return.
        // if k > 1 recursion -> if remain <= 0, return.

        // exit
        if (s > 9 || k < 1 || remain < 0) return;

        // last one
        if (k == 1) {
            for (int i = s; i <= 9; i++) {
                if (i < remain) {
                    continue;
                } else if (i == remain) {
                    note.add(i);
                    res.add(new ArrayList<Integer>(note));
                    note.remove(note.size()-1);
                    return;
                } else if (i > remain){
                    return;
                }
            }
            return;
        }

        // k > 1, continue recursion
        for (int i = s; i <= 9; i++) {
            if (i >= remain) return;
            note.add(i);
            backtrack(i+1, k-1, remain-i, note, res);
            note.remove(note.size()-1);
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        backtrack(1, k, n, res, new ArrayList<Integer>());
        return res;
    }

    private void backtrack(int start, int remainK, int remainN, List<List<Integer>> res, List<Integer> note) {
        if (remainK == 0) {  // up to k numbers
            if (remainN == 0) { // add up to number n
                res.add(new ArrayList<Integer>(note));
            }
            return;
        }

        for (int i = start; i <= 9; i++) {
            note.add(i);
            backtrack(i+1, remainK-1, remainN - i, res, note);
            note.remove(note.size()-1);
        }
    }
}