LeetCode | 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/递归获得所有组合。

代码

import java.util.ArrayList;

public class Combinations {
	private ArrayList<ArrayList<Integer>> results;
	private int n;
	private int k;

	public ArrayList<ArrayList<Integer>> combine(int n, int k) {
		results = new ArrayList<ArrayList<Integer>>();
		this.n = n;
		this.k = k;
		dfs(0, 1, new ArrayList<Integer>());
		return results;
	}

	private void dfs(int level, int start, ArrayList<Integer> list) {
		if (level == k) {
			results.add(new ArrayList<Integer>(list));
			return;
		}
		for (int i = start; i <= n; ++i) {
			ArrayList<Integer> temp = new ArrayList<Integer>(list);
			temp.add(i);
			dfs(level + 1, i + 1, temp);
		}
	}
}

LeetCode | Combinations,布布扣,bubuko.com

原文：http://blog.csdn.net/perfect8886/article/details/21488185