力扣小白刷题之216题组合总和Ⅲ

题目描述

找出所有相加之和为n 的 k 个数的组合。组合只允许含有 1-9 的正整数，并且每种组合中不存在重复的数字。

思路

参考自：https://leetcode-cn.com/problems/combination-sum-iii/solution/hui-su-jian-zhi-by-liweiwei1419/

1. 画图分析，看清剪枝和结算的条件
   
   1. 尝试做减法，减到 0 就说明可能找到了一个符和题意的组合 ，但是题目对组合里元素的个数有限制，因此还需要对元素个数做判断；
   2. 如果减到负数，也没有必要继续搜索下去；
   3. 因为结果集中的元素互不相同，因此下一层搜索的起点应该是上一层搜索的起点值 + 1。
2. 根据画出的递归树设计递归回溯方法
   1. 剩下的树的和是residue，初始的时候传入 n；
   2. 需要 k 个数。每递归一层，需要找的数就减去1，因此需要一个变量表示还需要搜索多少个数，仍用 k 表示，到 0 的时候表示搜索结束；
   3. 搜索的起点，最小是 1， 最大是 9，事实上，这个最大值有一个上界。 这里暂时忽略
   4. 需要一个变量 list 表示从根节点到叶子节点的路径：
      • 对象类型的状态变量(这里是 list)，在方法传递中是引用传递，在结算的时候要做一个拷贝；
      • 对象类型的状态变量(这里是 list)，在方法传递中是引用传递，在回溯的时候，要重置现场，这就是在 backtracking 前后，代码是对称的原因；
      • 基本类型的变量值(k, start, residue)，在方法传递中是值传递，每一次都用一个新的，因此，无需状态重置(恢复现场)。

代码

考虑更多剪枝