Find subsets whose sum=target

Find subsets whose sum=target

Problem: Given a set of numbers (in an integer array), the partition problem is to find a subset of the numbers that add up to a specific target number. For example, there are two ways to partition the set {1, 3, 4, 5} so that the remaining elements add up to 5.

{1, 4}

{5}

By contrast, there is no way to partition the set {1, 3, 4, 5} to get 11. Write a function NumberOfPartitions which takes an array of integers, and a target number, and returns the number of partitions of that set of integers which add up to the target.

int numPartitions(int[] array, int target);

Example: arr = {1, 3, 4, 5}, numPartitions(arr, 5) => 2, numPartitions(arr, 11) => 0

Problem

1. Can we have duplicate key in the array?

Read full article from Find subsets whose sum=target