原题链接：77. Combinations
【思路-Java、Python】递归实现 采用回溯算法。这是一道 NP 难问题，时间复杂度没办法提高，用一个循环递归处理子问题，问题的终止条件是每个组合中的元素个数达到 k 个： 【思路2-Python】非递归实现
26 / 26
test cases passed. Runtime: 3 ms Your runtime beats 56.70% of javasubmissions.
public class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();dfs(res, temp, n, k, 1);return res;}private void dfs(List<List<Integer>> res, List<Integer> temp, int n, int k, int m) {if(k == 0) {res.add(new ArrayList<Integer>(temp));return;}for(int i=m; i<=n; i++) {temp.add(i);dfs(res, temp, n, k-1, i+1);temp.remove(temp.size()-1);}}
}
26 / 26
test cases passed. Runtime: 88 ms Your runtime beats 32.21% of pythonsubmissions.
class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""res = []self.rec(res, 0, n, k, [])return resdef rec(self, res, i, n, k, temp) :if k == 0 :res.append(temp)returnfor j in range(i+1, n+1) :self.rec(res, j, n, k-1, temp+[j])
26 / 26
test cases passed. Runtime: 88 ms Your runtime beats 32.21% of pythonsubmissions.
class Solution(object):def combine(self, NN, K):""":type n: int:type k: int:rtype: List[List[int]]"""result = [[[]]]for n in range(1,NN+1):newRes=[[[]]]for k in range(1,n):newRes.append(result[k] + [i + [n] for i in result[k-1]])newRes.append([result[n-1][0] + [n]])result = newResreturn result[K]
更优解法可参考：优化解法
本文链接：https://my.lmcjl.com/post/8229.html
4 评论