55// Note:
66// All numbers (including target) will be positive integers.
77// The solution set must not contain duplicate combinations.
8- // For example, given candidate set [2, 3, 6, 7] and target 7,
9- // A solution set is:
8+ // For example, given candidate set [2, 3, 6, 7] and target 7,
9+ // A solution set is:
1010// [
1111// [7],
1212// [2, 2, 3]
2424 */
2525var combinationSum = function ( candidates , target ) {
2626var result = [ ] ;
27-
27+
2828if ( candidates === null || candidates . length === 0 ) {
2929return result ;
3030}
31-
31+
3232candidates . sort ( function ( a , b ) { return a > b ?1 :- 1 } ) ;
33-
33+
3434var output = [ ] ;
35-
35+
3636generate ( candidates , result , output , target , 0 ) ;
37-
37+
3838return result ;
3939} ;
4040
4141var generate = function ( candidates , result , output , sum , index ) {
4242if ( sum === 0 ) {
43- result . push ( output . slice ( ) ) ;
43+ result . push ( output . slice ( ) ) ;
4444}
4545if ( sum < 0 ) {
4646return ;
4747}
48-
48+
4949for ( var i = index ; i < candidates . length ; i ++ ) {
5050if ( i > index && candidates [ i ] === candidates [ i - 1 ] ) {
5151continue ;
5252}
53-
53+
5454if ( candidates [ i ] <= sum ) {
5555output . push ( candidates [ i ] ) ;
5656generate ( candidates , result , output , sum - candidates [ i ] , i ) ;
5757output . pop ( ) ;
5858}
5959}
60- }
60+ }
61+
62+
63+ // Another solution
64+ var combinationSum = function ( candidates , target ) {
65+ var results = [ ] ;
66+ comb ( candidates . sort ( ) , 0 , [ ] , 0 , target , results ) ;
67+ return results ;
68+ } ;
69+
70+ var comb = function ( cand , index , partial , partialSum , target , results ) {
71+ if ( target === partialSum ) {
72+ results . push ( partial ) ;
73+ return ;
74+ }
75+ if ( cand . length === index || partialSum > target ) {
76+ return ;
77+ }
78+
79+ comb ( cand , index + 1 , partial , partialSum , target , results ) ;
80+ comb ( cand , index , partial . concat ( [ cand [ index ] ] . concat ( [ cand [ index ] ] ) ) ,
81+ partialSum + 2 * cand [ index ] , target , results ) ;
82+ comb ( cand , index + 1 , partial . concat ( [ cand [ index ] ] ) ,
83+ partialSum + cand [ index ] , target , results ) ;
84+ } ;