Combinations

LeetCode 77 | Difficulty: Medium

Medium

Problem Description

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

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

- `1 <= n <= 20`

- `1 <= k <= n`

Topics: Backtracking

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

---

Solutions

Solution 1: C# (Best: 244 ms)

Metric	Value
Runtime	244 ms
Memory	29.8 MB
Date	2020-01-10

Solution

public class Solution {
    public IList<IList<int>> Combine(int n, int k) {
      List<IList<int>> result = new List<IList<int>>();
    int[] vals = Enumerable.Range(1,n).ToArray();
    List<int> temp = new List<int>();
    backtrack(result, n, k, vals, temp, 0);
    return result;
}

void backtrack(List<IList<int>> result,int n, int k, int[] vals, List<int> temp, int index)
{
    if(temp.Count == k)
    {
        result.Add(temp.ToList());
        return;
    }
    //if(n-index+1>=k)
    for (int i = index; i < vals.Length; i++)
    {
        //if(temp.Contains(vals[index])) continue;
        temp.Add(vals[i]);
        backtrack(result,n,k,vals, temp, i+1);
        temp.RemoveAt(temp.Count-1);
    }
    
    
}
}

📜 1 more C# submission(s)

Submission (2018-01-26) — 531 ms, N/A

public class Solution {
    public IList<IList<int>> Combine(int n, int k) {
      List<IList<int>> dp = new List<IList<int>>();
    CombineBackTrack(dp, new List<int>(), 1, n, k);
    return dp;
}

public void CombineBackTrack(List<IList<int>> combinations, List<int> templist, int start, int n, int k)
{
    if(k==0) 
    {
        combinations.Add(templist.ToList());    
    }
    if(n-start+1>=k)
    for (int i=start; i <= n; i++)
        {
            templist.Add(i);
            CombineBackTrack(combinations, templist,i+1, n, k-1);
            templist.RemoveAt(templist.Count-1);
        }

}
}

---

Complexity Analysis

Approach	Time	Space
Backtracking	$O(n! or 2^n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Identify pruning conditions early to avoid exploring invalid branches.