s*******m
发帖数: 228 | 1 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
2+3， 3+2 两个，所以return 2
开始想到了hashmap，走了弯路，发现不对转回到dfs
写完之后followup：
怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
branch，应该怎么处理？
-----------
排序后，没看出来有重复的branch |
g****o
发帖数: 547 | 2 我觉得应该先排序
2 3 7
你不该是从2开始dfs找到2 3
然后3开始dfs找到3 2，这样重复了
而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
另外也可以dp
dp[target][n]代表用前n个数加出target的可能数
dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1] |
s*******m
发帖数: 228 | 3 那要对每个结果，都做个permutation.
可行。
排序后，dfs找到一个结果就直接剪枝了。
似乎不用优化了吧
【在 g****o 的大作中提到】
: 我觉得应该先排序
: 2 3 7
: 你不该是从2开始dfs找到2 3
: 然后3开始dfs找到3 2，这样重复了
: 而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
: 另外也可以dp
: dp[target][n]代表用前n个数加出target的可能数
: dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1]
|
F****n
发帖数: 3271 | 4 除非本来就是排好序的或有空间要求
否则排序至少O(nlogn), 用hastable O(n)
【在 s*******m 的大作中提到】
: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch
|
n******n
发帖数: 12088 | 5 hash是捷径，怎么弯路了？
【在 s*******m 的大作中提到】
: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch
|
n******n
发帖数: 12088 | 6 DFS才是错误的
【在 s*******m 的大作中提到】
: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch
|
s*******m
发帖数: 228 | 7 求解释，
那是别人的面经。
【在 n******n 的大作中提到】
: DFS才是错误的
|
r****7
发帖数: 2282 | 8 排序不排序没有影响
如果没有重复元素就没有重复branch，有重复元素就有
【在 s*******m 的大作中提到】
: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch
|
C****t
发帖数: 53 | 9 一个hashtable就好， key为元素，value为两个数【重复次数，visited的状态】
def total(nums, tar):
maps = {}
res = 0
for ele in nums:
if ele not in maps:
maps[ele] = [1,0]
else:
maps[ele][0] += 1
for ele in nums:
if maps[ele][1] = 1: continue
diff = tar - ele
if diff not in maps: continue
rep1, rep2 = maps[ele][0], maps[diff][0]
if ele == diff and rep1 > 1:
res += rep1*(rep1-1)//2
elif ele != diff:
res += rep1*rep2
maps[ele][1] = 1
maps[diff][1] = 1
return res |
r****7
发帖数: 2282 | 10 搞笑吧，你当成2sum了？
【在 C****t 的大作中提到】
: 一个hashtable就好， key为元素，value为两个数【重复次数，visited的状态】
: def total(nums, tar):
: maps = {}
: res = 0
: for ele in nums:
: if ele not in maps:
: maps[ele] = [1,0]
: else:
: maps[ele][0] += 1
: for ele in nums:
|
|
|
n******n
发帖数: 12088 | 11 2sum变种啊。
【在 r****7 的大作中提到】
: 搞笑吧，你当成2sum了？
|
s*******m
发帖数: 228 | 12 不是two sum.
是leetcode的combination sum.
只不过，一个的解的排列，也都是解
【在 n******n 的大作中提到】
: 2sum变种啊。
|
n******n
发帖数: 12088 | 13 就是说不止两个数？你给的例子误导。
那就排序再递归喽。
【在 s*******m 的大作中提到】
: 不是two sum.
: 是leetcode的combination sum.
: 只不过，一个的解的排列，也都是解
|
a*********0
发帖数: 2727 | 14 dp得全是正数吧，负数怎么整?
【在 g****o 的大作中提到】
: 我觉得应该先排序
: 2 3 7
: 你不该是从2开始dfs找到2 3
: 然后3开始dfs找到3 2，这样重复了
: 而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
: 另外也可以dp
: dp[target][n]代表用前n个数加出target的可能数
: dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1]
|
s*******m
发帖数: 228 | 15 面经中没讲，应该没有负数。
有的话
dfs还好使不？
【在 a*********0 的大作中提到】
: dp得全是正数吧，负数怎么整?
|
s*******m
发帖数: 228 | 16 对啊，只求个数，dp就可以了吧。
【在 a*********0 的大作中提到】
: dp得全是正数吧，负数怎么整?
|
k****r
发帖数: 807 | 17 use DP
int CountWays(vector A, int target) {
vector dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; ++i) {
for (auto a : A) {
if (i >= a) {
dp[i] += dp[i - a];
}
}
}
return dp[k];
}
【在 s*******m 的大作中提到】
: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch
|
s*******m
发帖数: 228 | 18 dp 怎么计算
2,3;;; 3,2 这样的情况呢
【在 g****o 的大作中提到】
: 我觉得应该先排序
: 2 3 7
: 你不该是从2开始dfs找到2 3
: 然后3开始dfs找到3 2，这样重复了
: 而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
: 另外也可以dp
: dp[target][n]代表用前n个数加出target的可能数
: dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1]
|
w*****d
发帖数: 105 | 19 先dp把unique的combination数得到。
对于每个combination，算permutation数。所有permutation的和就是你要的结果了。
算combination的算法大家都说了，我就不重复了。
算permutation的话，需要知道总个数n，和每个元素的重复个数，比如：1个a， 2个b
， 3个c，...，那么：
permutation = n! / (1! * 2! * 3! * ...)
【在 s*******m 的大作中提到】
: dp 怎么计算
: 2,3;;; 3,2 这样的情况呢
|
s*******m
发帖数: 228 | 20 不能用1维dp吧，
因为dp[i-a]的已经被覆盖掉了
【在 k****r 的大作中提到】
: use DP
: int CountWays(vector A, int target) {
: vector dp(target + 1, 0);
: dp[0] = 1;
: for (int i = 0; i <= target; ++i) {
: for (auto a : A) {
: if (i >= a) {
: dp[i] += dp[i - a];
: }
: }
|
H*******g
发帖数: 6997 | 21 弱问下，着算是TWO SUM的变形么？
俺今天才知道啥叫TWO SUM,哈哈
【在 s*******m 的大作中提到】
: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch
|
