2017/07/23 Update
今天做這題發(fā)現(xiàn)這種for+遞歸并不是我想象的n*n模型兰迫，第二個n是堆棧深度弱卡，完全取決于你什么時候return峦阁，如果不return就會stackOverFlow辆飘。N queens是N*N因為人為制定了終止條件是n龄捡。
這題第一次做還是去年了卓嫂。。Intellij里顯示著：Created by DrunkPiano on 2016/12/30. 那時候還沒有寫簡書聘殖，這里補上晨雳。
轉(zhuǎn)眼已經(jīng)4個月過去了。第一次寫這題時候的心情郁悶死了就斤，根本不知道dfs干嘛悍募，恢復(fù)現(xiàn)場干嘛。洋机。練習(xí)真是有用的坠宴，我現(xiàn)在有種感覺就是無論做什么事情只有你在上面花了工夫了才會出點成果，比如彈吉他绷旗，再沒有天分的人 天天練的話也能練好一首曲子喜鼓。但是還有些例外，就是同樣是投入練習(xí)衔肢，有的人會彈得好庄岖，有的人會彈得差；打dota也一樣角骤，有的人打了幾年還是菜雞隅忿，這就不僅僅是練習(xí)了心剥，如果除去天分的話，影響成果的就是練習(xí)的方法背桐，比如是否善于總結(jié)优烧，會不會對某個點進行針對性訓(xùn)練等等。
再寫這道題的時候思路很清楚链峭，用全排列(permuattions)的那種一層層遞歸的套路畦娄。但是漏掉了一個問題，就是忘記讓for的初始值再進入下一層的時候不能從自己之前的數(shù)開始弊仪，否則就duplicated了熙卡，例如這樣一個case：
Input:
[2,3,6,7]
7
Output:
[[2,2,3],[2,3,2],[3,2,2],[7]]
Expected:
[[2,2,3],[7]]
這題跟N皇后其實有相似之處，最終都會形成一個n * n的matrix的遍歷形式励饵，很清晰的DFS驳癌，為什么要讓i = start也很清楚：
最后貼下代碼，注意
if(i>0 && candidates[i] == candidates[i-1]) continue;這句可以把提高一些速度曲横。
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) return result;
dfs(target, new ArrayList<Integer>(), candidates , 0);
return result;
}
private void dfs(int target, List<Integer> item, int[] candidates, int start) {
if (target < 0) return;
if (target == 0) {
result.add(new ArrayList<>(item));
return;
}
for (int i = start; i < candidates.length; i++) {
// //加上下面這句對結(jié)果沒有影響喂柒，但會減少很多次循環(huán)，因為同一個數(shù)字可以復(fù)用（每次從i開始）禾嫉，所以重復(fù)數(shù)字就沒有意義了
if(i>0 && candidates[i] == candidates[i-1]) continue;
item.add(candidates[i]);
dfs(target - candidates[i], item, candidates, i);
item.remove(item.size() - 1);
}
}
