import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Source : https://oj.leetcode.com/problems/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],
* ]
*
*/
public class Combination {
private List<Integer[]> result = null;
/**
* 求排列组合Cnk
* 使用递归求解
* 或者使用针对每一位寻找剩余位数
* @param n
* @param k
* @return
*/
public List<Integer[]> combine (int n, int k) {
result = new ArrayList<Integer[]>();
List<Integer> list = new ArrayList<Integer>();
combineByRecursion(n, 1, k, list);
return result;
}
public List<Integer[]> combine1 (int n, int k) {
result = new ArrayList<Integer[]>();
List<Integer> list = new ArrayList<Integer>();
combineByRecursion1(n, k, list);
return result;
}
/**
* 从前向后递归
* @param n
* @param start
* @param k
* @param list
*/
public void combineByRecursion (int n, int start, int k, List<Integer> list) {
if (k == 0) {
Integer[] newList = new Integer[list.size()];
System.arraycopy(list.toArray(new Integer[list.size()]), 0, newList, 0, list.size());
result.add(newList);
return;
}
for (int i = start; i <= n; i++) {
list.add(i);
combineByRecursion(n, i + 1, k - 1, list);
list.remove(list.size() - 1);
}
}
/**
* 从后向前递归
* @param n
* @param k
* @param list
*/
public void combineByRecursion1 (int n, int k, List<Integer> list) {
if (k == 0) {
Integer[] newList = new Integer[list.size()];
System.arraycopy(list.toArray(new Integer[list.size()]), 0, newList, 0, list.size());
result.add(newList);
return;
}
for (int i = n; i > 0; i--) {
list.add(i);
combineByRecursion1(i - 1, k - 1, list);
list.remove(list.size() - 1);
}
}
/**
* 不使用递归，使用循环
* @param n
* @param k
*/
public void combine2 (int n, int k) {
for (int i = 1; i <= n-k; i++) {
for (int j = i + 1; j < n-k; j++) {
}
}
}
public static void print (List<Integer[]> list) {
for (Integer[] arr : list) {
System.out.println(Arrays.toString(arr));
}
System.out.println();
}
public static void main(String[] args) {
Combination combination = new Combination();
print(combination.combine(4, 2));
print(combination.combine1(4, 2));
}
}