How to generate all possible list from given range of list which will target given input sum

Question

Input: Target sum

Output: count of all possible permutations with given sum from list [1,2,3]

Example input: 4 and corresponding output: 7

All possible pairs:

For these given permutations for explanation of output these all must be taken from [1,2,3] for any input.

Here is what I've tried so far:

def combinationSum(self, candidates, target):

    rests = [[] for _ in range(target)]
    for num in candidates:
        if num > target:
            continue
        else:
            rests[target - num].append([num])
        for cur_rest in range(target - 1, num - 1, -1):
            for result in rests[cur_rest]:
                rests[cur_rest - num].append(result + [num])

    return rests[0]

s=Solution()
c=[1,2,3]
t=int(input())
print(s.combinationSum(c,t))

Welcome to StackOverFlow! Have a look on [How to create a Minimal, Reproducible Example](https://stackoverflow.com/help/reprex) and what is a [good question](https://stackoverflow.com/help/how-to-ask). You will even have rewards at visiting those pages. We will not write code for you/do your home work. Share what you have tried so far and we will try to improve it. — shaik moeed, Jul 12 '19 at 11:55
def combinationSum(self, candidates, target): rests = [[] for _ in range(target)] for num in candidates: if num > target: continue else: rests[target - num].append([num]) for cur_rest in range(target - 1, num - 1, -1): for result in rests[cur_rest]: rests[cur_rest - num].append(result + [num]) return rests[0] s=Solution() c=[1,2,3] t=int(input()) print(s.combinationSum(c,t)) — GurpreetKaur Daughter of Guru, Jul 12 '19 at 11:56
Please put this code inside your question by pressing the `edit` button under the tags. Comments lose the format — Tomerikoo, Jul 12 '19 at 11:56
I have one doubt after reading your NOTE. Is list will always be same as [1,2,3] for any input number, lets say 230 ? — Parikshit Chalke, Jul 12 '19 at 12:01
Possible duplicate of [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum) — Tomerikoo, Jul 12 '19 at 12:06
https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum — GurpreetKaur Daughter of Guru, Jul 12 '19 at 12:22
Possible duplicate of [Find all combinations of list elements including duplicate elements](https://stackoverflow.com/questions/50239927/find-all-combinations-of-list-elements-including-duplicate-elements) — Georgy, Jul 12 '19 at 12:55

score 0 · Answer 1 · answered Jul 12 '19 at 12:59

As per solution suggested by @Tomerikoo, I have created solution with some modification.

    def combinationSum(self, candidates, target):
        # List for storing possible all sequence of permutations
        seq_list = []

        # This loop will generate all possible permutation for given candidates
        for i in range(1, target + 1):
           # Extend given list with cartesian product of given candidates

           # To calculate cartesian product set use itertools.product with candidates
           # with set size ranging from 1 to target number
           # This is necessary as we have to find all possible combinations
           seq_list.extend([p for p in itertools.product(candidates, repeat=i)])

        # Just select those sequence whose sum is target
        result = [seq for seq in seq_list if sum(seq) == target]

        # Return length of result set
        return len(result)

s=Solution() 
c=[1,2,3] 
t=int(input()) 
print(s.combinationSum(c,t))

Hope this help!!!

How to generate all possible list from given range of list which will target given input sum

1 Answers1