216 组合总和 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. 回溯算法
组合问题用回溯算法解决，将该题想想成一个9叉树。

1-9的9叉树
9叉树的遍历可以参考二叉树，代码如下：

    private void dfs(一些参数) {
        //递归必须要有终止条件
        if ("终止条件") {
            //1，执行一些操作（可有可无，视情况而定）
            return;
        }
        //通过循环，分别遍历9个子树,二叉树是分别遍历左右节点
        for (int i = 0; i <= 9; i++) {
            //2，一些操作，可有可无，视情况而定

            //递归
            dfs(一些参数);
            //3，一些操作，可有可无，视情况而定
        }
    }

递归主要分为递与归的过程，也就是往下传递与往回走，以斐波那契数列为例。

斐波那契数列

所以本题也一样，往下传递的时候我们要把当前节点的值加入到一个集合中，并且用n减去当前节点的值，返回的时候再把它给移除掉就行了。那么终止条件是什么呢，就是集合中的size等于k，并且n等于0。

代码

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

/**
 * 组合总和3
 */
public class CombinationSum3 {
    public List<List<Integer>> combinationSum3(int k, int n){
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, new ArrayList<>(), k, 1, n);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n){
        //终止条件,当加入list的数量==k，或者n==0,不用找了,找到合适的了
        if (list.size() == k && n == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        //注意这里，因为不能有重复的集合以及集合中不能有重复的数字，所以这里的i不能从0开始，
        // 要从上一个选择之后的下一个值开始
        for (int i=start; i<=9; i++){
            //递过程
            list.add(i);
            //递归
            dfs(res, list, k, i+1, n-i);
            //返回过程
            list.remove(list.size()-1);
        }
    }
}