hoho的日子

Given a   set   of candidate numbers ( C )   (without duplicates)   and a target number ( T ), find all unique combinations in   C   where the candidate numbers sums to   T . The   same   repeated number may be chosen from   C   unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set   [2, 3, 6, 7]   and target   7 ,   A solution set is:   [ [7], [2, 2, 3] ] 可以把這題想成 找錢問題, 現在 要找客人 7 塊, 手上有 面額 2,3,6,7 的硬幣無限個 請問有幾種找法. 因為是找錢 所以[2,2,3] 跟 [2,3,2] 是一樣的. 想法上還是 dfs, line_8 : 錢多找了, 答案一定不對. 直接就放棄不找了 加快收尋速度 line_10 : path 做深copy, line_14 : n[i:] 就是避免循環的時候 出現重複選的情況. [2,2,3] 跟 [2,3,2] 就是在這被過濾掉的

Find all possible combinations of   k   numbers that add up to a number   n , given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input:   k   = 3,   n   = 7 Output: [[1,2,4]] Example 2: Input:   k   = 3,   n   = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] 從 1 - 9 個數字裡選擇 k 個數字的 和(加總) 為 n. 考慮還是用深度優先來做. line_5: path 裡的個數為 k, 然後加總為 target 符合題目需求 line_7: res 加上 深copy. 創造新的 list 並加入到 res line_9: 遍歷數字 1 - 9 line_10 - 12: dfs 遞歸  

Given two integers   n   and   k , return all possible combinations of   k   numbers out of 1 ...   n . For example, If   n   = 4 and   k   = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 題目簡單明瞭, 我們要找出所有的組合 以上面的範例來說就是 在1,2,3,4 中取兩個數字組成一個組合. 這裡要注意的是 [1,3] 和 [3,1] 算是同一個組合.所以不能重複計算. 我們用DFS來解, line 5: 有個testcase: 20取 16 會超時. 這裡我們可以早點停止尋找  如果剩下的可選數字 不能填滿組合 就剪枝(backtracking). remaining elements is smaller than needed to fill combination line 7: path 裡的數字滿足 k. 用deep copy 複製一個新的list 然後加到res去 line 10 -12 : dfs