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 楼
完全背包结果去重
相关阅读
2013 h1b几天用完？Re: 推荐书＜卢瑟经济学＞，中国发展出版社，2012年9月出版 (转 (转载)MySQL如何查看query执行时间？有必要将O1签证转成H1B签证吗？大家圣诞快乐！圣诞节装了win8，感觉很不错，感谢微软的童鞋！G 家电面面经这期非诚勿扰就是qualcomm EE高富帅秒杀湾区CS屌丝码农 (转载)突然发现下个星期三个technical screen已毕业在找工作,看不到希望, 求refer,求信息,感谢!Amex SPG卡送25K points 免费送500刀现金 最佳酒店卡OPT renewal A-Number 那一栏该怎么填？[合集] 纯谈钱，码工和教授！问一个关于跳槽到甲方的问题问道面试题刚毕业，有offer了，两个月能拿到opt吗？CPT/OPT 一问,多谢啦!岁末，在这里挖一个职场经历的大坑amazon SDE1算什么职位？还是contractor，是难还是entry level？Bloomberg电面题目+ 攒RP for onsite公司让先用CPT做临时full-time，拿到OPT再转正式的，请教CPT,OPT 可以overlap吗？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。