Leetcode 216 combined summation III -- backtracking method

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/combination-sum-iii

---

The question ：

Find the sum of all the sums n Of k Combination of numbers . Only allowed in combination 1 - 9 The positive integer , And there are no duplicate numbers in each combination .

explain ：
All numbers are positive integers .
A solution set cannot contain duplicate combinations .

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

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

---

Reference article

Ideas ：

In fact, if you do 《LeetCode 77 Combine 》 This question , This question is actually easier . It is suggested that this problem 《LeetCode 77 Combine 》 Just do it , They all use the backtracking method and do simple pruning .

The pruning of this topic is reflected in for In circulation sum+i<=n On this conditional statement .

This topic Java Code ：

class Solution {
    
    int sum;
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    private void backTracking(int k, int n, int start) {
    
        if (path.size() == k) {
    
            if (sum == n) ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= 9 && sum + i <= n; i++) {
    
            path.add(i);
            sum += i;
            backTracking(k, n, i + 1);
            sum -= i;
            path.removeLast();
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
    
        backTracking(k, n, 1);
        return ans;
    }
}