216. 组合总和III

回溯

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {

    List> list = new ArrayList<>();
    LinkedList li = new LinkedList<>();

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

        backtracking(k, n, 1);
        return list;
    }

    public void backtracking(int k, int n, int startIndex){

        /**
         * 终止条件
         */
        if (li.size() == k && n == 0) {

            list.add(new ArrayList<>(li));
            return;
        }
        
        if (li.size() >= k || n < 0){
            return;
        }

        for (int i = startIndex; i < 10; i++) {

            li.add(i);
            backtracking(k, n - i, i + 1);
            li.removeLast();
        }
    }
}

/**
 * 时间复杂度 O(((n/k)×k)
 * 空间复杂度 O(k)
 */

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