2020-05-02 216. Combination Sum

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.

Note:

All numbers will be positive integers.

The solution set must not contain duplicate combinations.

Example 1:

Input:k= 3,n= 7Output:[[1,2,4]]

Example 2:

Input:k= 3,n= 9Output:[[1,2,6], [1,3,5], [2,3,4]]

有个trick： (2 * i + k - 1) / 2 <= n

因为不这样提前判断好，会浪费时间做一些不必要的遍历

注意进入下一层遍历的时候，n取n-i，k取k-1

class Solution {

    public List<List<Integer>> combinationSum3(int k, int n) {

        List<List<Integer>> res = new LinkedList<>();

        List<Integer> cur = new ArrayList<>();

        backtrace(cur, res, k, n, 1);

        return res;

    }

    private void backtrace(List<Integer> cur, List<List<Integer>> res, int k, int n, int start) {

        if (n <= 0 || k <= 0) {

            if (n == 0 && k == 0) res.add(new ArrayList<>(cur));

            return;

        }

        for (int i = start; i <= 9 && (2 * i + k - 1) / 2 <= n; i++) {

            cur.add(i);

            backtrace(cur, res, k - 1, n - i, i + 1);

            cur.remove(cur.size() - 1);

        }

    }

}