leetcode刷題筆記(Golang)--216. Combination Sum III

216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers.

The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7

Output: [[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output: [[1,2,6], [1,3,5], [2,3,4]]

func combinationSum3(k int, n int) [][]int {
	graph := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
	res := [][]int{}
	dfs(graph, 0, n, k, []int{}, &res)
	return res
}

func dfs(graph []int, curr int, target int, lg int, path []int, paths *[][]int) {
	if target == 0 && len(path) == lg {
		tmp := make([]int, lg)
		copy(tmp, path)
		*paths = append(*paths, tmp)
		return
	}
	for i := curr; i < len(graph); i++ {
		dfs(graph, i+1, target-graph[i], lg, append(path, graph[i]), paths)
	}
}