Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- // Function to calculate the number of subsets with a given sum
- public int perfectSum(int[] nums, int target) {
- int n = nums.length;
- // step-1 create a matrix
- int[][] t = new int[n+1][target+1];
- // step-2 intialise the matrix with base condition
- for(int i=0; i<n+1; i++)
- {
- for(int j=0; j<target+1; j++)
- {
- // when we reach last index of the array, so no subset found
- if(i == 0)
- t[i][j] = 0;
- // when target sum becomes 0, we found a subset
- if(j == 0)
- t[i][j] = 1;
- }
- }
- // step-3 convert recursive code into iterative
- for(int i=1; i<n+1; i++)
- {
- for(int j=0; j<target+1; j++)
- {
- if(nums[i-1] <= j)
- {
- int pick = t[i-1][j - nums[i-1]];
- int notPick = t[i-1][j];
- t[i][j] = pick + notPick;
- }
- else
- t[i][j] = t[i-1][j];
- }
- }
- return t[n][target];
- }
- }
RAW Paste Data
Copied
