題目?jī)?nèi)容

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], ] 題目鏈接

題目簡(jiǎn)介

寫(xiě)出給定范圍整數(shù)的所有組合

題目分析

用迭代法。以全零數(shù)列開(kāi)始迭代，從首元素開(kāi)始進(jìn)行如下迭代。 1.該數(shù)自增1。 2.若元素大于n，指針前移一位，回循環(huán)體頭部； 若已是末尾元素，記錄該組合； 否則把該元素的值賦給后一元素。指針后退一位返回循環(huán)體頭部。

實(shí)際模擬后發(fā)現(xiàn)該過(guò)程可視為從首元素為1，公差為1的等差數(shù)列的迭代過(guò)程。 從末尾元素開(kāi)始對(duì)每個(gè)元素進(jìn)行遞增，若每數(shù)均小于n且成功到達(dá)末尾元素，則記錄組合；若超出范圍則將指針后退，對(duì)前一元素進(jìn)行遞增。 根據(jù)歸納法可知該方法可以不遺漏不重復(fù)地記錄所有合法組合。

代碼示例