LeetCode-in-Go

77. Combinations

Medium

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

Solution

func combine(n int, k int) [][]int {
	ans := make([][]int, 0)
	if n > 20 || k < 1 || k > n {
		return ans
	}
	backtrack(&ans, n, k, 1, make([]int, 0))
	return ans
}

func backtrack(ans *[][]int, n, k, s int, stack []int) {
	if k == 0 {
		*ans = append(*ans, append([]int{}, stack...))
		return
	}
	for i := s; i <= (n-k)+1; i++ {
		stack = append(stack, i)
		backtrack(ans, n, k-1, i+1, stack)
		stack = stack[:len(stack)-1]
	}
}

This site is open source. Improve this page.