# Concise python solution using DFS

• ``````class Solution:
# @param {integer} k
# @param {integer} n
# @return {integer[][]}
def combinationSum3(self, k, n):
if n > sum([i for i in range(1, 11)]):
return []

res = []
self.sum_help(k, n, 1, [], res)
return res

def sum_help(self, k, n, curr, arr, res):
if len(arr) == k:
if sum(arr) == n:
res.append(list(arr))
return

if len(arr) > k or curr > 9:
return

for i in range(curr, 10):
arr.append(i)
self.sum_help(k, n, i + 1, arr, res)
arr.pop()``````

• Similar approach:

``````class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
self.output = []
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
self.compute([], arr, k, n)
return self.output

def compute(self, pre, post, k, n):
if len(pre) == k and n == 0:
self.output.append(pre)
elif n < 0 or len(pre) > k:
return
else:
for i in range(0, len(post)):
self.compute(pre+[post[i]], post[i+1:], k, n-post[i])
``````

• Why you have to use list(arr) ? Isn't 'arr' already a list ?

• sum([i for i in range(1,11)]) ???
shouldn't it be range(1,10)??

• I replace the line `if n > sum([i for i in range(1, 11)])` with `if n > sum([i for i in range(10-k, 10)]):`
It looks like better

• @swengzju You should make a copy of arr and add it to res rather than directly append arr to res. Otherwise any change in arr would change res too.

• few lines of code can be simplified.

``````class Solution:
# @param {integer} k
# @param {integer} n
# @return {integer[][]}
def combinationSum3(self, k, n):
res = []
self.sum_help(k, n, 1, [], res)
return res

def sum_help(self, k, n, curr, arr, res, curr_sum=0):
if len(arr) == k:
if curr_sum == n:
res.append(arr[:])
return
if curr_sum >= n:
return

for i in xrange(curr, 10):
arr.append(i)
self.sum_help(k, n, i + 1, arr, res, curr_sum + i)
arr.pop()
``````

• res.append(list(arr))

In the statement above

If I remove "list", I get a wrong result.

Why??

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.