0

Basically, I am trying to implement combination sum II in python using dynamic programming, my goal was to create a program that does not have a time complexity of O(2^n) but I have been having a lot of issues and am unable to find solutions anywhere. The following is the code I have gotten so far, but it does not seem to give any output.

Expected output: [1,2,3],[1,5],[2,4]

Actual output: literally nothing

arr = [1,2,3,4,5]
def combinationSum(candidates, target):

    counts = [0] * (target + 1)
    for elem in candidates:
        if elem <= target:
            counts[elem] += 1
            
    numbers = []

    a = 1
    while a <= target:
        if counts[a] != 0:
            numbers.append(a)
        a += 1

    subsets = [[]] * (target+1)
    smallTarget = numbers[0]
    while smallTarget <= target:
        subset = []

        for i in numbers:
            if i > smallTarget:
                break
            if (((i == smallTarget) or (i <= smallTarget/2)) != True) :
                continue

            mList = subsets[smallTarget - i]

            for j in mList:
                if len(j) == 0 or j[0] >= i:

                    count = counts[number]

                    for k in j:

                        if k == i :
                            count -= 1
                    if count != 0:
                        tList = []

                        tList.append(i)

                        for l in j:
                            tList.append(l)
                            
                        subset.add(tList)
        subsets[smallTarget] = subset
        smallTarget+=1
    return subsets[target]


for i in combinationSum(arr, 6):
    print(i)
Parth Agarwal
  • 9
  • 1
  • Are you looking for the pseudopolynomial dynamic programming solution? [This problem is known as subset sum](https://en.wikipedia.org/wiki/Subset_sum_problem) and is NP-hard, although there [several previous questions](https://stackoverflow.com/questions/18818406/find-a-solution-to-subset-sum-using-dynamic-programming) on pseudopolynomial DP solutions. Otherwise, no sub-exponential algorithm is known. – kcsquared Sep 06 '21 at 02:13
  • Alright, thanks for the info will look into it and see what I can find – Parth Agarwal Sep 06 '21 at 03:33

1 Answers1

2

To fix your code not printing answers, add an empty subset summing to 0 before your loop:

subsets[0].append([])

after subsets is created.

There are, however, several problems with this code, from variable names to repeated work. Take a look at several other approaches to the subset sum problem or just google "Subset sum" to see many existing solutions to your problem.

kcsquared
  • 5,244
  • 1
  • 11
  • 36