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> results;
	private int n;
	private int k;

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

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