c*******r
发帖数: 309 | 1 给一个array 都是 positive， 给一个 sum， 输出所有的 subarray 加和是 sum
这题应该咋解？ 用recursion?准备了小半年发现水平依然是菜比。。 | b*****u
发帖数: 648 | | p*****2
发帖数: 21240 | | r**h
发帖数: 1288 | 4 backtrack，由于是全正数因此可以剪枝
dp的话可以判断是否存在subset但是输出所有可能结果不方便
【在 c*******r 的大作中提到】
: 给一个array 都是 positive， 给一个 sum， 输出所有的 subarray 加和是 sum
: 这题应该咋解？ 用recursion?准备了小半年发现水平依然是菜比。。
| c*****a
发帖数: 808 | 5 dfs 啊
leetcode 的 combination sum 2啊 | c*******r
发帖数: 309 | 6 多谢各位了......想起来以前看到leetcode的题是用backtrack来解的。 这个DFS我再
消化消化 | s*******n
发帖数: 97 | 7 题目好像说的是subarray吧？如果是这样,累加求和，然后binary search, O(nlogn) | j********x
发帖数: 2330 | 8 双指针的窗口移动，考虑全是正数，这应该是最直观的解法
subarray和一类的题目可以考虑用prefix array sum的方法在常数时间内求得，这个方
法在很多跟array matrix有关的题目里都用得上
楼上几位能介绍一下dfs怎么做么？ | r**h
发帖数: 1288 | 9 题目不要求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], nSum);
pSub[nIndex] = 0;
findSubSetSum(pArr, pSub, nSize, nIndex+1, curSum, nSum);
}
}
【在 j********x 的大作中提到】
: 双指针的窗口移动，考虑全是正数，这应该是最直观的解法
: subarray和一类的题目可以考虑用prefix array sum的方法在常数时间内求得，这个方
: 法在很多跟array matrix有关的题目里都用得上
: 楼上几位能介绍一下dfs怎么做么？
|
|
