🌕 216. 组合总和 III

难度: 🌕

问题描述

---

解法

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 思路：
        // 回溯 + 剪枝
        // 特殊情况特判
        if(k >= n) {
            return res;
        }
        LinkedList<Integer> path = new LinkedList<>();
        mySol(k, n, 1, 0, path);
        return res;
    }

    private void mySol(int k, int target, int index, int sum, LinkedList<Integer> path) {
        // 递归终止条件
        if(path.size() == k) {
            if(sum == target) {
                res.add(new LinkedList<>(path));
            }
            return;
        }
        if(index > 9 || sum >= target) {
            return;
        }
        // size() < k
        for(int i = index; i <= 10 - k + path.size(); i ++) {
            path.addLast(i);
            mySol(k, target, i + 1, sum + i, path);
            path.removeLast();
        }
    }
}

---

输出