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

原问题链接：https://leetcode.com/problems/combinations/

 

问题分析

    关于这个问题在之前一篇讨论排列组合的文章里有讨论过。求给定数字范围的组合时，它遵循一个如下的关系：

void combine(源数据集合a, 目的数据集合b, 当前迭代起始点begin, 当前目标数据集合位置cur, int n) {
    if(cur == n)
       //输出数组b
    for（集合a中间从begin到end的元素i) {
        b[cur] = a[i];
        combine(a, b, i + 1, cur + 1, n);
    }
}

   概括起来说就是每次我们从一个给定的位置上开始往后取元素，取了一个元素之后继续在它后面的位置递归的取下一个元素。这样就形成了集合取元素的组合。在详细的实现里我们用一个list保存当前取了的元素，采用拷贝构造传递上一个调用的参数。详细的实现如下：

 

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        combine(n, k, 1, result, new ArrayList<>());
        return result;
    }

    public void combine(int n, int k, int start, List<List<Integer>> result, ArrayList<Integer> l) {
        if(k == 0) {
            result.add(l);
            return;
        }
        for(int i = start; i <= n; ++i) {
            ArrayList<Integer> a = new ArrayList<>(l);
            a.add(i);
            combine(n, k - 1, i + 1, result, a);
        }
    }
}

    在上述的实现里，通过在递归的函数里不断创建新的数组，但是新建的数组又是基于原有参数的基础创建的。这种传递的手法有点类似于immutable的实现思路。值得仔细推敲。