77. Combinations

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:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]

思路： 采用回溯算法。这是一道 NP 难问题，时间复杂度没办法提高，用一个循环递归处理子问题，问题的终止条件是每个组合中的元素个数达到 k 个。

class Solution { public List> combine(int n, int k) { List> res = new ArrayList>(); List temp = new ArrayList(); dfs(res, temp, n, k, 1); return res; } private void dfs(List> res, List temp, int n, int k, int m) { if(k == 0) { res.add(new ArrayList(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); } } }

class Solution { public List> combine(int n, int k) { int[] num = new int[n]; for(int i = 0; i < n; i++) num[i] = i+1; List> result = new ArrayList<>(); dfs(num, result, new ArrayList<>(), 0, k); return result; } private void dfs(int[] nums, List> set, List list, int i, int k) { if(list.size() == k) { set.add(new ArrayList<>(list)); return; } if(i == nums.length) return; list.add(nums[i]); dfs(nums, set, list, i+1, k); list.remove(list.size() - 1); dfs(nums, set, list, i+1, k); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。