建设银行网站怎么修改手机号码,猎头用什么网站做单,网络营销五种方法,wordpress更换域名图片给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意#xff1a;解集不能包含重复的组合。
思路一#xff1a;回溯
int cmp(const …给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
思路一回溯
int cmp(const void* a, const void* b){return *(int*)a - *(int*)b;
}int** Result NULL;
int* rtcolsizes NULL;
int Result_Index 0;int Path[30] {0};
int Path_Index 0;int* Source NULL;
int Source_Size 0;void Back_Track(int target, int idx){if(target 0){int* temi (int*)malloc(sizeof(int) * Path_Index);memcpy(temi, Path, Path_Index * sizeof(int));Result[Result_Index] temi;rtcolsizes[Result_Index] Path_Index;Result_Index;return;}for(int i idx; i Source_Size; i){if(i idx Source[i] Source[i - 1]){continue;}if(target - Source[i] 0){break;}Path[Path_Index] Source[i];Path_Index;Back_Track(target - Source[i], i 1);Path_Index--;}
}int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){qsort(candidates, candidatesSize, sizeof(int), cmp);Result (int**)malloc(sizeof(int*) * 48);rtcolsizes (int*)malloc(sizeof(int) * 48);Result_Index 0;Path_Index 0;Source candidates;Source_Size candidatesSize;Back_Track(target, 0);*returnSize Result_Index;*returnColumnSizes rtcolsizes;return Result;
}
分析
该题要求和为target的组合可先将原数组排序后进行递归回溯处理。将数组中目标数不断减去小于目标数的数直到等于0时将这些存储到准备好的数组中再返回数组。实际编写的时候需注意加的数的赋给result的时候要path存储加的数。
总结
本题主要考察了回溯算法的应用使用递归将加的组合数找出。
