Skip to content

Instantly share code, notes, and snippets.

@supritashankar
Created June 16, 2016 07:11
Show Gist options
  • Save supritashankar/4c77aa1e6ae41aa794863a8735e04859 to your computer and use it in GitHub Desktop.
Save supritashankar/4c77aa1e6ae41aa794863a8735e04859 to your computer and use it in GitHub Desktop.
Find the bug in this program?!
"""
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.
For example: if n = 7 k = 3
ans [1,2,4]
k = 3 n = 9
[[1,2,6], [1,3,5], [2,3,4]]
"""
class CombinationArray(object):
def __init__(self):
return
def combination3(self,n,k):
ans = []
self.result = []
self.combinationrec(ans, k, 1, n)
return self.result
def combinationrec(self, ans, k, start, n):
if n == 0 and len(ans) == k:
self.result.append(ans)
return
for i in range(start, 10):
ans.append(i)
self.combinationrec(ans, k, i+1, n-i)
ans.pop()
if __name__ == '__main__':
c = CombinationArray()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment