Combination

This technique uses backtracking to find combinations in an input data.

How to Identify

• Data Structure Involves: Array, String
• Question Type: When you need to find the combinations of a given set.

Example

Combinations

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

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.

Typescript

function combine(n: number, k: number): number[][] {
    const result: number[][] = []

    function backtracking(start: number, comb: number[]){
        // base case
        if(comb.length === k) {       // if the combination is done
            result.push(comb.slice())
            return
        }

        // recursive case
        for(let i=start; i<=n; i++){
            comb.push(i)               // add i into the current combination
            backtracking(i+1, comb)    // use next integers to complete the combination
            comb.pop()                 // backtrack
        }
    }

    backtracking(1, [])
    return result
}

Related Problems

	Problems	Difficulty
1	Combinations	Medium
2	Combination Sum	Medium
3	Combination Sum II	Medium
4	Letter Combinations of a Phone Number	Medium