Count number of subsets with a given sum

Problem Link: https://www.codingninjas.com/codestudio/problems/number-of-subsets_3952532?leftPanelTab=0

def findWays(nums: List[int], target: int) -> int:
    # Write your code here.
    n=len(nums)
    dp=[[0 for i in range(target+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(target+1):
            if(i==0):
                dp[i][j]=0
            if(j==0):
                dp[i][j]=1
            else:
                if(nums[i-1]<=j):
                    inc=dp[i-1][j-nums[i-1]]
                    exc=dp[i-1][j]
                    dp[i][j]=(inc + exc)
                else:
                    dp[i][j]=dp[i-1][j]

    return dp[n][target]

Last updated