[LeetCode 77] Combinations(精妙的迭代）

题目内容

77.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], ] 题目链接

题目简介

写出给定范围整数的所有组合

题目分析

用迭代法。以全零数列开始迭代，从首元素开始进行如下迭代。 1.该数自增1。 2.若元素大于n，指针前移一位，回循环体头部； 若已是末尾元素，记录该组合； 否则把该元素的值赋给后一元素。指针后退一位返回循环体头部。

实际模拟后发现该过程可视为从首元素为1，公差为1的等差数列的迭代过程。 从末尾元素开始对每个元素进行递增，若每数均小于n且成功到达末尾元素，则记录组合；若超出范围则将指针后退，对前一元素进行递增。 根据归纳法可知该方法可以不遗漏不重复地记录所有合法组合。

代码示例