LeetCode 216. 组合总和 III

和77. 组合差不多，区别在于这题目是求k个数之和=n，并且不存在重复的数字。

思路：回溯三部曲：

1. 定义两个全局变量，result存放结果集，path存放如何条件的结果。 startIndex 记录下一层递归搜索的起始位置。
2. 终止条件：当到达叶子节点，即pathTop == k时，result收集path，return。
3. 单层搜索过程。处理节点、递归函数、回溯 *** 作。
   关于剪枝 *** 作：画图可以观察出，要完成剪枝 *** 作，只需在单层搜索过程中改动即可。
   搜索起点的上界 = n-还需要的元素个数 +1; 即 j<= n (k-pathTop) + 1;

int *path;
int pathTop;
int **result;
int resultTop;

void backTrack(int k,int n,int sum ,int startIndex){
    if(pathTop==k){
        if(n == sum){
            int *temp = malloc(sizeof(int)*k);
            for(int i =0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5670372.html