# 77. Combinations

題目：<https://leetcode.com/problems/combinations/>

解法：backtracking，依序由小到大放入數字，放滿後記錄，接著往回前一個繼續放入其他數字，直到所有數字都放完。

Python3：

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        def backtrack(step):
            if step == k:
                output.append(list(cur))
                return
            for num in range(cur[-1]+1, n+1):
                cur.append(num)
                backtrack(step + 1)
                cur.pop()
        
        output = []
        for num in range(1, n+1):
            cur = [num]
            backtrack(1)
        return output

if __name__ == '__main__':
    n = 4
    k = 2

    ans = Solution().combine(n, k)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    *returnSize = 1;
    for (int i = 1; i <= k; i++) {
        *returnSize *= (n - k + i);
        *returnSize /= i;
    }
    int ** output = (int**)malloc(sizeof(int*) * (*returnSize));
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < (*returnSize); i++) {
        (*returnColumnSizes)[i] = k;
        output[i] = (int*)malloc(sizeof(int) * k);
    }
    int count = 0;
    int cur[k];
    
    void backtrack(int step) {
        if (step == k) {
            for (int i = 0; i < k; i++)
                output[count][i] = cur[i];
            count++;
            return;
        }
        for (int num = cur[step-1]+1; num <= n; num++) {
            cur[step] = num;
            backtrack(step + 1);
        }
    }
    
    for (int num = 1; num <= n; num++) {
        cur[0] = num;
        backtrack(1);
    }
    return output;
}

int main()
{
    int n = 4, k = 2;
    int returnSize;
    int *returnColumnSizes;
    int ** ans = combine(n, k, &returnSize, &returnColumnSizes);
    printf("%d\n", returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d: ", returnColumnSizes[i]);
        for (int j = 0; j < returnColumnSizes[i]; j++)
            printf("%d ", ans[i][j]);
        printf("\n");
    }
    return 0;
}

###### tags: `leetcode` `backtracking`