LeetCode 216. 组合总和 III

力扣

1. 求出个数为 k 的所有组合
2. 筛选和为 n 的组合

public class CombinationSum3 {

    public int sum = 0;
    public LinkedList pathList = new LinkedList<>();
    public List> resultList = new ArrayList<>();

    public List> combinationSum3(int k, int n) {
        dfsForCombinationSum3(k, n, 1);
        return resultList;
    }

    private void dfsForCombinationSum3(int k, int n, int start) {
        if (pathList.size() == k && sum == n) {
            resultList.add(new ArrayList<>(pathList));
            return;
        }

        // 剪枝1：上限最大值
        int maxIndex = Math.min(n - sum, 9);
        int needNumber = k - pathList.size();
        for (int i = start; i <= maxIndex; i++) {
            // 剪枝2：元素个数
            if (maxIndex - i + 1 < needNumber) {
                continue;
            }

            sum += i;
            pathList.add(i);

            dfsForCombinationSum3(k, n, i+1);

            sum -= i;
            pathList.removeLast();
        }
    }
}

剪枝：

1. 当前组合的和为 sum，总和为 n，带选择组合和应该为 (n-sum)，所以 for 遍历上限应该小于等于  (n-sum)，因为题目要求从 [1,9] 选择数字，所以 for 遍历上限应该为：Math.min((n-sum), 9)。
2. k 是元素总数，path.size() 是已选择元素总数，(k-path.size()) 为待选择的元素总数，(maxIndex-i+1) 为未选择的元素总数，如果 (maxIndex-i+1) < (k-path.size()) 表示剩下的元素数量小于需要元素数量，即使将剩下元素全部选上，总数也不足 k，所以不再进行后续遍历。