package Ġcom . daily . algo th rim . leetcode . medium Ċ Ċ /** Ċ Ġ* Ġ 3 9 . Ġ ç»ĦåĲĪ æĢ» åĴĮ Ċ Ġ* Ċ Ġ* Ġ ç»Ļ å®ļ ä¸Ģä¸ª æĹł éĩįå¤į åħĥç´ł çļĦ æķ°ç»Ħ Âł candidates Âł åĴĮ ä¸Ģä¸ª çĽ®æłĩ æķ° Âł target Âł ï¼Į æī¾ åĩº Âł candidates Âł ä¸Ń æīĢæľī åı¯ä»¥ ä½¿ æķ°åŃĹ åĴĮ ä¸º Âł target Âł çļĦ ç»ĦåĲĪ ãĢĤ Ċ Ġ* Ġcandidates Âł ä¸ŃçļĦ æķ°åŃĹ åı¯ä»¥ æĹł éĻĲåĪ¶ éĩįå¤į è¢« éĢī åıĸ ãĢĤ Ċ Ġ* Ċ Ġ* Ġ è¯´æĺİ ï¼ļ Ċ Ġ* Ċ Ġ* Ġ æīĢæľī æķ°åŃĹ ï¼Ī åĮħæĭ¬ Âł target ï¼ī éĥ½æĺ¯ æŃ£ æķ´æķ° ãĢĤ Ċ Ġ* Ġ è§£ éĽĨ ä¸įèĥ½ åĮħåĲ« éĩįå¤į çļĦ ç»ĦåĲĪ ãĢĤ ÂłĊ Ġ*/ Ċ class ĠCombin ation Sum Ġ{ ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġ@ Jvm Static ĊĠĠĠĠĠĠĠ Ġfun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠCombin ation Sum (). combin ation Sum ( int ArrayOf ( 2 , Ġ 3 , Ġ 6 , Ġ 7 ), Ġ 7 ). forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . forEach Ġ{ Ġitem Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprint ( item ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠCombin ation Sum (). combin ation Sum ( int ArrayOf ( 2 , Ġ 3 , Ġ 5 ), Ġ 8 ). forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . forEach Ġ{ Ġitem Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprint ( item ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġ è¾ĵåħ¥ ï¼ļ candidates Ġ= Ġ[ 2 , 3 , 6 , 7 ], Ġtarget Ġ= Ġ 7 , ĊĠĠĠ Ġ// Ġ æīĢ æ±Ĥ è§£ éĽĨ ä¸º ï¼ļ ĊĠĠĠ Ġ// Ġ[ ĊĠĠĠ Ġ// Ġ Ġ[ 7 ], ĊĠĠĠ Ġ// Ġ Ġ[ 2 , 2 , 3 ] ĊĠĠĠ Ġ// Ġ] ĊĠĠĠ Ġfun Ġcombination Sum ( candidates : ĠInt Array , Ġtarget : ĠInt ): ĠList < List < Int >> Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( candidates . isEmpty ()) Ġreturn ĠlistOf () ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġarray ListOf < List < Int >>() ĊĠĠĠĠĠĠĠ Ġback tracking ( target , Ġcandidates , Ġ 0 , Ġarray ListOf (), Ġresult ) ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġback tracking ( ĊĠĠĠĠĠĠĠ Ġrem ind : ĠInt , ĊĠĠĠĠĠĠĠ Ġcandidates : ĠInt Array , ĊĠĠĠĠĠĠĠ Ġindex : ĠInt , ĊĠĠĠĠĠĠĠ Ġcurrent List : ĠArrayList < Int >, ĊĠĠĠĠĠĠĠ Ġresult : ĠArrayList < List < Int >> ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( rem ind Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsub List Ġ= Ġarray ListOf < Int >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsub List . addAll ( current List ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( sub List ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( rem ind Ġ< Ġ 0 Ġ|| Ġindex Ġ>= Ġcandidates . size ) Ġreturn ĊĊĠĠĠĠĠĠĠ Ġback tracking ( rem ind , Ġcandidates , Ġindex Ġ+ Ġ 1 , Ġcurrent List , Ġresult ) ĊĠĠĠĠĠĠĠ Ġcurrent List . add ( candidates [ index ]) ĊĠĠĠĠĠĠĠ Ġback tracking ( rem ind Ġ- Ġcandidates [ index ], Ġcandidates , Ġindex , Ġcurrent List , Ġresult ) ĊĠĠĠĠĠĠĠ Ġcurrent List . remove At ( current List . size Ġ- Ġ 1 ) ĊĠĠĠ Ġ} Ċ }