r**h 发帖数: 1288 | 1 题目不要求subarray是连续的吧
DFS,就是根据每个节点(取或者不取)两种情况向后搜索并记录当前的解。由于题目
里面提到数组中所有元素都是正数,因此如果当前的和已经大于sum那么就可以直接剪枝
void findSubSetSum(int *pArr, int *pSub, int nSize, int nIndex, int curSum,
int nSum){
//剪枝
if(curSum+pArr[nIndex] > nSum)
return;
//找到解
if(curSum+pArr[nIndex] == nSum){
pSub[nIndex] = 1;
printResult(pArr, pSub, nIndex);
pSub[nIndex] = 0;
return;
}
//继续向后搜索,分两种情况
if(nIndex < nSize-1){
pSub[nIndex] = 1;
findSubSetSum(pArr, pSub, nSize, nIndex+1, curSum+pArr[nIndex... 阅读全帖 |
|