JAVA算法：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合（JAVA）
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。、
当 n = 4 ，k = 2 时；
结果为：[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
算法设计
package com.bean.algorithmbasic;import java.util.LinkedList;import java.util.List;public class CombinationsDemo5 {/** n = 4 and k = 2* 结果: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]* */// 全局变量，存储返回结果private List<List<Integer>> ret = new LinkedList<List<Integer>>();public List<List<Integer>> combine(int n, int k) {// 非法条件：一旦出现以下条件，直接返回空if (n <= 0 || k <= 0 || k > n)return ret;// 初始化一个可能结果c，当前c为空；c中存储一个可能的组合结果（c这个链表在整个过程是会变的）LinkedList<Integer> c = new LinkedList<Integer>();// 调用递归函数generateCombination(n, k, 1, c);// 返回结果return ret;}// 递归函数private void generateCombination(int n, int k, int start, LinkedList<Integer> c) {/*** @param n:* 题目中给的n* @param k:* 题目中给的k* @param start:* 从1-n中的第start个数开始往后考虑组合问题* @param c:* 存储一个可能的组合结果**/// 递归终止条件if (c.size() == k) {// 添加结果ret.add((LinkedList<Integer>) c.clone());return;}// 递归过程// start：从start这个数开始考虑组合问题// 截止当前，c中已经存储了c.size()个元素，因此还需要 k - c.size()个元素才可以完成组合寻找// 意味着从[i...n]中间要存在k - c.size()个数才有解，否则的话当前组合解中不可能凑够k个值// 因此为了保证[i...n]至少有k - c.size()个解，就需要i <= n - (k - c.size())for (int i = start; i <= n - (k - c.size()) + 1; i++) {c.addLast(i);generateCombination(n, k, i + 1, c);c.removeLast(); // 回溯}}public static void main(String[] args) {// TODO Auto-generated method stubCombinationsDemo5 cd = new CombinationsDemo5();int n = 4;int k = 2;List<List<Integer>> list = bine(n, k);System.out.println(list.toString());}}
