combinations_sum_III

hitzzc · hitzzc · commit 310e9431c86b · 2016-10-17T00:04:38.000+08:00
diff --git a/README.md b/README.md
@@ -173,6 +173,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [213. House Robber II](https://github.com/hitzzc/go-leetcode/tree/master/add_and_search_word)
 #### [214. Shortest Palindrome (unsolved)](https://github.com/hitzzc/go-leetcode/tree/master/shortest_palindrome)
 #### [215. Kth Largest Element in an Array](https://github.com/hitzzc/go-leetcode/tree/master/kth_largest_element_in_an_array)
+#### [216. Combination Sum III](https://github.com/hitzzc/go-leetcode/tree/master/combinations_sum_III)
 
 
 
diff --git a/combinations_sum_III/combinations_sum_III.go b/combinations_sum_III/combinations_sum_III.go
@@ -0,0 +1,21 @@
+package combinations_sum_III
+
+func combinationSum3(k int, n int) [][]int {
+	return DFS(0, 1, k, n, []int{})
+}
+
+func DFS(level int, start int, k int, n int, path []int) (ret [][]int) {
+	if level == k && n == 0 {
+		cp := make([]int, len(path))
+		copy(cp, path)
+		ret = append(ret, cp)
+		return
+	}
+	for i := start; i <= n && i <= 9; i++ {
+		path = append(path, i)
+		tmpRet := DFS(level+1, i+1, k, n-i, path)
+		ret = append(ret, tmpRet...)
+		path = path[:len(path)-1]
+	}
+	return
+}
