[LeetCode] 77. Combinations
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:
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
留言
張貼留言