贾考博 LeetCode 39. Combination Sum

[@azfa3605]

官方解答给出时间复杂度是O(N^(T/M)+1), N: # of candidates; T: target value; M: minimum number in candidates. 相当于dfs遍历一个高度为T/M 的 N-ary tree,节点个数为N^(T/M)+1.

[@liangemma2699]

讲的真好，时间复杂度分析的也特别详细。

[@zy3749]

感觉你讲的是最清楚的

[@yi-shenglien4783]

不懂 Line#18 為什麼要 remove

[@jing9792]

public static List combinationSum(int[] candidates, int target) { List res = new ArrayList(); helper(candidates, res, target, new ArrayList(), 0); return res; } private static void helper(int[] nums, List res, int target, List temp, int start) { if (target < 0) return; if (target == 0) { res.add(new ArrayList(temp)); return; } for (int i = start; i < nums.length; i++) { temp.add(nums[i]); System.out.println("Adding " + nums[i] + " at index " + i + " - Current Temp List: " + temp); helper(nums, res, target - nums[i], temp, i); temp.remove(temp.size() - 1); System.out.println("Removing " + nums[i] + " at index " + i + " - Current Temp List: " + temp); } } 你run這段程式碼你大概就會懂了

[@123-f2r8v]

因為要回溯，這其實就是深度優先搜索的應用，發現無路可走的時候就要退出

[@yi-shenglien4783]

感謝大大回覆

[@andyzhang9789]

backtracking 这一类题目都挺难的啊，好像就没有easy的题，受益匪浅

[@ouo9454]

受益良多，但反而我開始擔心起自己數學了...

[@dede6110]

no need sort in the video but in your code page there is sort

[@jiakaobo]

更新中…

[@dede6110]

@@jiakaobo 因为其他解法看到有用到sort 而你的这个写法可以不用 太牛了

[@weiyisun4519]

讲得太好了！！感谢！

[@kevinwang3981]

标准模版