LeetCode_ Backtracking_ Medium_ 216. Combined sum III

1. subject

Find the sum of all the sums n Of k Combination of numbers , And the following conditions are met ：
① Use only numbers 1 To 9
② Each number can be used at most once
Returns a list of all possible valid combinations . The list cannot contain the same combination twice , Combinations can be returned in any order .

Example 1：
Input : k = 3, n = 7
Output : [[1,2,4]]
explain :
1 + 2 + 4 = 7
There is no other matching combination .

Example 2：
Input : k = 3, n = 9
Output : [[1,2,6], [1,3,5], [2,3,4]]
explain :
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There is no other matching combination .

Example 3：
Input : k = 4, n = 1
Output : []
explain : There is no valid combination .
stay [1,9] Use... In scope 4 A different number , The minimum sum we can get is 1 + 2 + 3 + 4 = 10, because 10 > 1, No valid combination .

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

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

2. Ideas

（1） to flash back
This question is very similar to the following two questions , Just modify the previous code slightly .
LeetCode_ to flash back _ secondary _39. Combinatorial summation
LeetCode_ to flash back _ secondary _40. Combinatorial summation II

3. Code implementation （Java）

// Ideas 1———— to flash back 
class Solution {
    
    // res  Used to save the final results 
    List<List<Integer>> res = new ArrayList<>();
    
    // track  Path used to record backtracking 
    ArrayList<Integer> track = new ArrayList<>();
    
    public List<List<Integer>> combinationSum3(int k, int n) {
    
        int[] candidates = {
    1, 2, 3, 4, 5, 6, 7, 8, 9};
        int minSum = 0;
        int maxSum = 0;
        for (int i = 0; i < k; i++) {
    
            minSum += candidates[i];
            maxSum += candidates[candidates.length - i - 1];
        }
        // Judgement boundary 
        if (n > maxSum || n < minSum) {
    
            return res;
        }
        backtrack(candidates, 0, n, 0, k);
        return res;
    }
    
    public void backtrack(int[] candidates, int start, int target, int sum, int k) {
    
        if (sum == target && track.size() == k) {
    
            // Find target combination , Save it to  res  in 
            res.add(new ArrayList<>(track));
            return;
        }
        if (sum > target || track.size() > k) {
    
            // The sum of combined elements exceeds  target  Or use more than  k, End directly 
            return;
        }
        // Backtracking algorithm framework 
        for (int i = start; i < candidates.length; i++) {
    
            // To make a choice 
            sum += candidates[i];
            track.add(candidates[i]);
            /* backtrack( route ,  Selection list )  It should be noted that , Array  candidates  Elements in can only be used once , So when looking down in the backtracking tree , Starting from  i + 1 */
            backtrack(candidates, i + 1, target, sum, k);
            // Unselect 
            sum -= candidates[i];
            track.remove(track.size() - 1);
        }
    }
}