Brooke

一、題目

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

 

Example 1:

Input: n = 4, k = 2 Output: [  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4], ]

Example 2:

Input: n = 1, k = 1 Output: [[1]]

 

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

 

二、程式作法

 public class Solution
{
    public IList<IList<int>> res = new List<IList<int>>();
    public int n = 0;
    public int k = 0;
    public IList<IList<int>> Combine(int n, int k)
    {
        this.n = n;
        this.k = k;

        ToCombine(1, new List<int>());
        return res;
    }

    public void ToCombine(int currNum, List<int> l)
    {
        if (l.Count == k)
            res.Add(new List<int>(l));
        else
        {
            for (int i = currNum; i <= n; i++)
            {
                l.Add(i);
                ToCombine(i + 1, l);
                l.RemoveAt(l.Count - 1);
            }
        }
    }
}

 

三、思路筆記

實在看不懂那英文題目指的是要做何事，直到看他的範例才有些了解，

題目為一組 k 的元素，請列出元素值 1 ~ n 之間，可產生多少種組合？

更白話來說，n 個元素，每次取 k 個，請問共可產生多少種組合？

使用 Backtracking 來處理。