216. 组合总和 III

题目地址(216. 组合总和 III)

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

题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

前置知识

公司

• 暂无

思路

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
相对于77. 组合，无非就是多了一个限制，本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,…,9]。
想到这一点了，做过77. 组合之后，本题是简单一些了。
本题k相当于了树的深度，9（因为整个集合就是9个数）就是树的宽度。
例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（个数） = 2, n（和） = 4的组合。

返回值和参数

返回值就是void
接下来还需要如下参数：

• n（int）目标和，题目中的n。
• k（int）就是题目中要求k个数的集合。
• sum（int）为已经收集的元素的总和，也就是path里元素的总和。

• startIndex（int）为下一层for循环搜索的起始位置。

  终止条件

  在上面已经说了，k其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义。
  所以如果path.size() 和 k相等了，就终止。
  如果此时path里收集到的元素和（sum） 和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。

  单层搜索过程

  和之前的差不多 就是for循环固定i<=9
  别忘了处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！

  剪枝

  已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉
  
  for循环的范围也可以剪枝，i <= 9 - (k - path.size()) + 1就可以了。

  关键点

• 
  

代码

• 语言支持：Java

Java Code:
直接暴力回溯还没剪枝就超过100%了 不过剪枝肯定更快

class Solution {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> combinationSum3(int k, int n) {
            loop(k, n, 1, 0);
            return res;
        }
        void loop(int k, int n , int startIndex , int sum){
            //剪枝 如果sum值大于总和了 就没有继续判断的必要了
            if (sum > n) {
                return;
            }
            //中止条件 判断path的大小是否等于k 等于的话在判断path的总和是否=n =的话就直接加到res里 最后都return
            if (path.size() == k) {
                if (sum == n) {
                    res.add(new ArrayList<>(path));
                }
                return;
            }
            for (int i = startIndex; i <= 9 -(k-path.size())+1 ; i++) {
                //path添加当前数字
                path.add(i);
                //总和加上当前数字
                sum +=i;
                //然后递归 看看递归里能不能找到符合的数
                loop(k, n, i+1, sum);
                //然后不管有没有找到 都要回溯 将之前的数据撤销 方便继续下一次循环
                sum -=i;
                path.removeLast();
            }
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=ZG9O0)
• 空间复杂度：#card=math&code=O%28n%29&id=aNVyf)