logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
求教 leetcode上OJ 的Combination Sum II 解法
avatar
求教 leetcode上OJ 的Combination Sum II 解法# JobHunting - 待字闺中
e*s
1 楼
Given a collection of candidate numbers (C) and a target number (T), find
all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … ,ak) must be in non-descending order.
(ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
avatar
p*2
2 楼
def dfs(l, start, list, sum):
if sum==0:
print list
return

if start==len(l) or sum<0:
return

prev=-1
for i in xrange(start,len(l)):
if l[i]!=prev:
list.append(l[i])
dfs(l,i+1,list,sum-l[i])
del list[-1]
prev=l[i]
l=[10,1,2,7,6,1,5]
k=8
l.sort()
list=[]
dfs(l,0,list,k)
avatar
e*s
3 楼
多谢二哥，请问有没有DP的方法？

【在 p*****2 的大作中提到】
: def dfs(l, start, list, sum):
: if sum==0:
: print list
: return
:
: if start==len(l) or sum<0:
: return
:
: prev=-1
: for i in xrange(start,len(l)):
avatar
C*U
4 楼
这个是不是和偷金子的问题一样
是NP的？

.

【在 e***s 的大作中提到】
: Given a collection of candidate numbers (C) and a target number (T), find
: all unique combinations in C where the candidate numbers sums to T.
: Each number in C may only be used once in the combination.
: Note:
: All numbers (including target) will be positive integers.
: Elements in a combination (a1, a2, … ,ak) must be in non-descending order.
: (ie, a1 ≤ a2 ≤ … ≤ ak).
: The solution set must not contain duplicate combinations.
: For example, given candidate set 10,1,2,7,6,1,5 and target 8,
: A solution set is:
avatar
p*2
5 楼

DP不能得到所有结果把？

【在 e***s 的大作中提到】
: 多谢二哥，请问有没有DP的方法？
avatar
e*s
6 楼
应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
3，2，1，1，4 TARGER: 2
1，1（这个答案就被去掉了)
2

【在 p*****2 的大作中提到】
:
: DP不能得到所有结果把？
avatar
p*2
7 楼

这种题一般不用dp做。除非只要总数，或最优。

【在 e***s 的大作中提到】
: 应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
: 3，2，1，1，4 TARGER: 2
: 1，1（这个答案就被去掉了)
: 2
avatar
e*s
8 楼
好的，感谢二哥

【在 p*****2 的大作中提到】
:
: 这种题一般不用dp做。除非只要总数，或最优。
avatar
y*u
9 楼
add
if (l[i] > sum):
break;
to the loop.

【在 p*****2 的大作中提到】
: def dfs(l, start, list, sum):
: if sum==0:
: print list
: return
:
: if start==len(l) or sum<0:
: return
:
: prev=-1
: for i in xrange(start,len(l)):
avatar
f*m
10 楼
对二哥的code我有个问题：
若原candidate中有两个1， 比如{1,1， 2, 3},那么用Prev会不会使得1只能被用一次？
比如start=0, l[0]被加到list中去，然后是递归dfs,接着prev被赋值为l[0],然后接着
for loop,此时l[1]和prev比较，因为l[1]也等于1，他等于prev,所以第二个1，也就是
l[1]，不会被加到list中去。这样,在最后的结果中只有一个1。但当target=2，输出结
果应该是{1,1},{2}。请指点。
谢谢。

【在 p*****2 的大作中提到】
: def dfs(l, start, list, sum):
: if sum==0:
: print list
: return
:
: if start==len(l) or sum<0:
: return
:
: prev=-1
: for i in xrange(start,len(l)):
avatar
S*1
11 楼
二哥 is correct.
Using prev is only to prevent using duplicated element in the same level.
For the deeper level, the prev was initially defined as -1, so the deeper
level will use the second 1.

次？

【在 f*********m 的大作中提到】
: 对二哥的code我有个问题：
: 若原candidate中有两个1， 比如{1,1， 2, 3},那么用Prev会不会使得1只能被用一次？
: 比如start=0, l[0]被加到list中去，然后是递归dfs,接着prev被赋值为l[0],然后接着
: for loop,此时l[1]和prev比较，因为l[1]也等于1，他等于prev,所以第二个1，也就是
: l[1]，不会被加到list中去。这样,在最后的结果中只有一个1。但当target=2，输出结
: 果应该是{1,1},{2}。请指点。
: 谢谢。
avatar
e*s
12 楼
Given a collection of candidate numbers (C) and a target number (T), find
all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … ,ak) must be in non-descending order.
(ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
avatar
p*2
13 楼
def dfs(l, start, list, sum):
if sum==0:
print list
return

if start==len(l) or sum<0:
return

prev=-1
for i in xrange(start,len(l)):
if l[i]!=prev:
list.append(l[i])
dfs(l,i+1,list,sum-l[i])
del list[-1]
prev=l[i]
l=[10,1,2,7,6,1,5]
k=8
l.sort()
list=[]
dfs(l,0,list,k)
avatar
e*s
14 楼
多谢二哥，请问有没有DP的方法？

【在 p*****2 的大作中提到】
: def dfs(l, start, list, sum):
: if sum==0:
: print list
: return
:
: if start==len(l) or sum<0:
: return
:
: prev=-1
: for i in xrange(start,len(l)):
avatar
C*U
15 楼
这个是不是和偷金子的问题一样
是NP的？

.

【在 e***s 的大作中提到】
: Given a collection of candidate numbers (C) and a target number (T), find
: all unique combinations in C where the candidate numbers sums to T.
: Each number in C may only be used once in the combination.
: Note:
: All numbers (including target) will be positive integers.
: Elements in a combination (a1, a2, … ,ak) must be in non-descending order.
: (ie, a1 ≤ a2 ≤ … ≤ ak).
: The solution set must not contain duplicate combinations.
: For example, given candidate set 10,1,2,7,6,1,5 and target 8,
: A solution set is:
avatar
p*2
16 楼

DP不能得到所有结果把？

【在 e***s 的大作中提到】
: 多谢二哥，请问有没有DP的方法？
avatar
e*s
17 楼
应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
3，2，1，1，4 TARGER: 2
1，1（这个答案就被去掉了)
2

【在 p*****2 的大作中提到】
:
: DP不能得到所有结果把？
avatar
p*2
18 楼

这种题一般不用dp做。除非只要总数，或最优。

【在 e***s 的大作中提到】
: 应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
: 3，2，1，1，4 TARGER: 2
: 1，1（这个答案就被去掉了)
: 2
avatar
e*s
19 楼
好的，感谢二哥

【在 p*****2 的大作中提到】
:
: 这种题一般不用dp做。除非只要总数，或最优。
avatar
y*u
20 楼
add
if (l[i] > sum):
break;
to the loop.

【在 p*****2 的大作中提到】
: def dfs(l, start, list, sum):
: if sum==0:
: print list
: return
:
: if start==len(l) or sum<0:
: return
:
: prev=-1
: for i in xrange(start,len(l)):
avatar
f*m
21 楼
对二哥的code我有个问题：
若原candidate中有两个1， 比如{1,1， 2, 3},那么用Prev会不会使得1只能被用一次？
比如start=0, l[0]被加到list中去，然后是递归dfs,接着prev被赋值为l[0],然后接着
for loop,此时l[1]和prev比较，因为l[1]也等于1，他等于prev,所以第二个1，也就是
l[1]，不会被加到list中去。这样,在最后的结果中只有一个1。但当target=2，输出结
果应该是{1,1},{2}。请指点。
谢谢。

【在 p*****2 的大作中提到】
: def dfs(l, start, list, sum):
: if sum==0:
: print list
: return
:
: if start==len(l) or sum<0:
: return
:
: prev=-1
: for i in xrange(start,len(l)):
avatar
S*1
22 楼
二哥 is correct.
Using prev is only to prevent using duplicated element in the same level.
For the deeper level, the prev was initially defined as -1, so the deeper
level will use the second 1.

次？

【在 f*********m 的大作中提到】
: 对二哥的code我有个问题：
: 若原candidate中有两个1， 比如{1,1， 2, 3},那么用Prev会不会使得1只能被用一次？
: 比如start=0, l[0]被加到list中去，然后是递归dfs,接着prev被赋值为l[0],然后接着
: for loop,此时l[1]和prev比较，因为l[1]也等于1，他等于prev,所以第二个1，也就是
: l[1]，不会被加到list中去。这样,在最后的结果中只有一个1。但当target=2，输出结
: 果应该是{1,1},{2}。请指点。
: 谢谢。
avatar
j*e
23 楼
没java解法么？
avatar
c*r
24 楼
what's the time complexity here? N power of N?
avatar
l*o
25 楼
完全背包结果去重
相关阅读
H1B正在RFE，EAD到期了，这种情况怎么处理？没绿卡，找工作，有多大困难？急！！！毁约：怎么样才能把人品损失降到最低opt extension empoloyer 的地址没填对会不会有问题？m家面经+求分析留在美国是越来越难了。。。出个题，求每个pair的hamming distance关于 应聘出版社工作，针对外国人的英语语言能力的笔试Re: 小型startup 职位推荐请教quit PhD找工作的问题求refer求教游戏公司UI电话面试～International travel before COS effective date面试问题 (转载)H1b 换工作中间有5天gap可以吗？H1b transfer期间可以出国么？如果现在有visa stamp。 (转载)H1B没中，公司说可以把我放在加拿大，这个可能吗怎么办？Can I leave U.S. after received the H-1B approval notice?有做过IT Business Relationship Manager的吗？弱问什么是电话screening？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。