Combinations (Java)

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

Solution: a classical DFS problem, pay attention to the format of solve this question which can be apply to many other DFS problems

	/*
	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],
	]
	Have you been asked this question in an interview?
	*/
	public class Solution {
	public ArrayList<ArrayList<Integer>> combine(int n, int k) {
	if (n<=0||k<=0){
	return null;
	}
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	int st=1;
	int num=0;
	ArrayList<Integer> subResult=new ArrayList<Integer>();
	buildResult(st, num, k, n, subResult, result);
	return result;
	}
	// DFS classical format
	private void buildResult(int start, int currentNum, int k, int n, ArrayList<Integer> subResult, ArrayList<ArrayList<Integer>> result)
	{
	if (currentNum==k){
	ArrayList<Integer> temp=new ArrayList<Integer>(subResult);
	result.add(temp);
	return;
	}
	for (int i=start; i<=n; i++){
	subResult.add(i);
	buildResult(i+1, currentNum+1, k, n, subResult, result);
	subResult.remove(subResult.size()-1);
	}
	}
	}

view raw Combinations.java hosted with ❤ by GitHub