[leetcode]Combinations

新博文地址：[leetcode]Combinations

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],
]

组合，今天排列组合求的略多啊。

DFS实现，哈哈，刚看了大神的DFS代码，就有题目拿来练手了，真心不错

 

	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	public ArrayList<ArrayList<Integer>> combine(int n,int k){
		if(n < 0 || k < 0 || n < k){
			return result;
		}
		for(int i = 1; i <= n - k + 1;i++){
			ArrayList<Integer> list = new ArrayList<Integer>();
			dfs(i,k,n,list);
		}
		return result;
	}//begin表示现在遍历到的数组元素，holdNum表示list.size()
	private void dfs(int begin,int k,int n,ArrayList<Integer> list){
		list.add(begin);
		if(list.size() == k ){//已经达到k个之后，将数组压入result
			ArrayList<Integer> copyList = new ArrayList<Integer>(list);
			result.add(copyList);
			return;
		}//否则就一直往下遍历各种可能
		for(int j = begin + 1; j <= n; j++){
			dfs(j, k, n, list);
			list.remove(list.get(list.size()-1));//回溯
		}
	}

  可读性不怎么好，如果不太明白的地方，欢迎吐槽