e***s
发帖数: 799 | 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] | p*****2
发帖数: 21240 | 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) | e***s
发帖数: 799 | 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)):
| C***U
发帖数: 2406 | 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:
| p*****2
发帖数: 21240 | 5
DP不能得到所有结果把？
【在 e***s 的大作中提到】
: 多谢二哥，请问有没有DP的方法？
| e***s
发帖数: 799 | 6 应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
3，2，1，1，4 TARGER: 2
1，1（这个答案就被去掉了)
2
【在 p*****2 的大作中提到】
:
: DP不能得到所有结果把？
| p*****2
发帖数: 21240 | 7
这种题一般不用dp做。除非只要总数，或最优。
【在 e***s 的大作中提到】
: 应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
: 3，2，1，1，4 TARGER: 2
: 1，1（这个答案就被去掉了)
: 2
| e***s
发帖数: 799 | 8 好的，感谢二哥
【在 p*****2 的大作中提到】
:
: 这种题一般不用dp做。除非只要总数，或最优。
| y****u
发帖数: 11 | 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)):
| f*********m
发帖数: 726 | 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)):
| | | S******1
发帖数: 269 | 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}。请指点。
: 谢谢。
| e***s
发帖数: 799 | 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] | p*****2
发帖数: 21240 | 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) | e***s
发帖数: 799 | 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)):
| C***U
发帖数: 2406 | 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:
| p*****2
发帖数: 21240 | 16
DP不能得到所有结果把？
【在 e***s 的大作中提到】
: 多谢二哥，请问有没有DP的方法？
| e***s
发帖数: 799 | 17 应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
3，2，1，1，4 TARGER: 2
1，1（这个答案就被去掉了)
2
【在 p*****2 的大作中提到】
:
: DP不能得到所有结果把？
| p*****2
发帖数: 21240 | 18
这种题一般不用dp做。除非只要总数，或最优。
【在 e***s 的大作中提到】
: 应该可以，但我的办法比较笨，要把index也记住做比较。因为如果只比较数值，
: 3，2，1，1，4 TARGER: 2
: 1，1（这个答案就被去掉了)
: 2
| e***s
发帖数: 799 | 19 好的，感谢二哥
【在 p*****2 的大作中提到】
:
: 这种题一般不用dp做。除非只要总数，或最优。
| y****u
发帖数: 11 | 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)):
| | | f*********m
发帖数: 726 | 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)):
| S******1
发帖数: 269 | 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}。请指点。
: 谢谢。
| j*******e
发帖数: 1058 | | c***r
发帖数: 35 | 24 what's the time complexity here? N power of N? | l****o
发帖数: 315 | |
|
