下面是一个简单易懂的递归c++解决方案:

#include<vector>
using namespace std;

template<typename T>
void ksubsets(const vector<T>& arr, unsigned left, unsigned idx,
    vector<T>& lst, vector<vector<T>>& res)
{
    if (left < 1) {
        res.push_back(lst);
        return;
    }
    for (unsigned i = idx; i < arr.size(); i++) {
        lst.push_back(arr[i]);
        ksubsets(arr, left - 1, i + 1, lst, res);
        lst.pop_back();
    }
}

int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5 };
    unsigned left = 3;
    vector<int> lst;
    vector<vector<int>> res;
    ksubsets<int>(arr, left, 0, lst, res);
    // now res has all the combinations
}

另一个具有组合索引惰性生成的c#版本。这个版本维护了一个索引数组来定义所有值列表和当前组合值之间的映射，即在整个运行时不断使用O(k)额外的空间。该代码在O(k)时间内生成单个组合，包括第一个组合。

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

测试代码:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

输出:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

下面的递归算法从有序集中选取所有k元素组合:

选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。

对集合中的每一个i进行上述迭代。

为了避免重复，您必须选择比i大的其余元素。这样[3,5]将只被选中一次，即[3]与[5]结合，而不是两次(该条件消除了[5]+[3])。没有这个条件，你得到的是变化而不是组合。

这里你有一个用c#编写的该算法的惰性评估版本:

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

及测试部分:

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

希望这对你有帮助!

另一种版本，迫使所有前k个组合首先出现，然后是所有前k+1个组合，然后是所有前k+2个组合，等等。这意味着如果你对数组进行排序，最重要的在最上面，它会把它们逐渐扩展到下一个——只有在必须这样做的时候。

private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
    if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
        return true;

    if (num[k - 1] + 1 == n)
        return false;

    ++num[k - 1];
    for (int i = 0; i < k - 1; ++i)
        num[i] = i;

    return true;
}

例如，如果你在k=3, n=5上运行第一个方法("nextCombination")，你会得到:

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

但如果你跑

int[] nums = new int[k];
for (int i = 0; i < k; ++i)
    nums[i] = i;
do
{
    Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));

你会得到这个(为了清晰起见，我添加了空行):

0 1 2

0 1 3
0 2 3
1 2 3

0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4

它只在必须添加时才添加“4”，而且在添加“4”之后，它只在必须添加时再添加“3”(在执行01、02、12之后)。

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

在c#中:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

用法:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

结果:

123
124
125
134
135
145
234
235
245
345