编程挑战：给定一个整数集[1，2，3，4，5]我想生成所有可能的K-组合中的升大小顺序在的Java ;例如，

Programming challenge: Given a set of integers [1, 2, 3, 4, 5] I would like to generate all possible k-combinations in ascending size order in Java; e.g.

[1], [2], [3], [4], [5], [1, 2], [1, 3] ... [1, 2, 3, 4, 5]

这是相当容易产生一个递归解决方案生成所有组合，然后对其进行排序之后，但我想有这么不再需要额外的排序更有效的方式。

It is fairly easy to produce a recursive solution that generates all combinations and then sort them afterwards but I imagine there's a more efficient way that removes the need for the additional sort.

推荐答案

我在想这方面的一些越来越意识到它可以高效地完成使用动态规划方法。下面是迭代的解决方案，我生产的，其采用了队列来保持状态（尽管可以使用堆栈代替）。

I was thinking about this some more and realised it can be efficiently done using a dynamic programming approach. Below is the iterative solution I've produced, which uses a Queue to hold state (although one could use a Stack instead).

我相信这是远远高于递归迭代深入搜索，因为它不涉及生成期间重新审查现有的国家更有效;它使用队列记住了previous状态，并利用它们产生连续的状态。

I believe this is far more efficient than a recursive iterative deepening search as it will not involve revisiting existing states during the generation; it remembers the previous states using the queue and uses these to generate successive states.

性能比较

Algorithm                    | 5 elems | 10 elems | 20 elems
--------------------------------------------------------------------------
Recursive (#recursions)      | 62      | 2046     | 2097150
Dynamic   (#loop iterations) | 32      | 1024     | 1048576

code

public class Test {
    private static class Pair {
        private final List<Integer> result;
        private final int index;

        private Pair(List<Integer> result, int index) {
            this.result = result;
            this.index = index;
        }

        public List<Integer> getResult() {
            return result;
        }

        public int getIndex() {
            return index;
        }
    }

    public static void main(String[] args) {
        List<Integer> items = Arrays.asList(1, 2, 3, 4, 5);
        foo(items);
    }

    private static void foo(List<Integer> items) {
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.add(new Pair(Collections.<Integer>emptyList(), 0));

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();

            System.err.println(pair.getResult());

            if (pair.getResult().size() < items.size()) {
                for (int i=pair.getIndex(); i<items.size(); ++i) {
                    List<Integer> copy = new LinkedList<Integer>(pair.getResult());
                    copy.add(items.get(i));
                    queue.add(new Pair(copy, i + 1));
                }
            }
        }
    }
}