Given a set of numbers: {1, 3, 2, 5, 4, 9}, find the number of subsets that sum to a particular value (say, 9 for this example).
This is similar to subset sum problem with the slight difference that instead of checking if the set has a subset that sums to 9, we have to find the number of such subsets. I am following the solution for subset sum problem here. But and I am wondering how I can modify it to return the count of subsets.
The usual DP solution is true for the problem.
One optimization you may do, is to keep a count of how many solutions exist for the particular sum rather than the actual sets that make up that sum...
This my dynamical programming implementation in JS. It will return an array of arrays, each holding the subsequences summing to the provided target value.
function getSummingItems(a,t){_x000D_
return a.reduce((h,n) => Object.keys(h)_x000D_
.reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))_x000D_
: m[k].map(sa => sa.concat(n)),m)_x000D_
: m, h), {0:[[]]})[t];_x000D_
}_x000D_
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]_x000D_
tgt = 42,_x000D_
res = [];_x000D_
_x000D_
console.time("test");_x000D_
res = getSummingItems(arr,tgt);_x000D_
console.timeEnd("test");_x000D_
console.log("found",res.length,"subsequences summing to",tgt);_x000D_
console.log(JSON.stringify(res));public class SumOfSubSet {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {1,2};
int sum=0;
if(a.length<=0) {
System.out.println(sum);
}else {
for(int i=0;i<a.length;i++) {
sum=sum+a[i];
for(int j=i+1;j<a.length;j++) {
sum=sum+a[i]+a[j];
}
}
System.out.println(sum);
}
}
}
This my program in ruby . It will return arrays, each holding the subsequences summing to the provided target value.
array = [1, 3, 4, 2, 7, 8, 9]
0..array.size.times.each do |i|
array.combination(i).to_a.each { |a| print a if a.inject(:+) == 9}
end
You may use Dynamic Programmining. Algo complexity is O(Sum * N) and use O(Sum) memory.
Here's my implementation in C#:
private static int GetmNumberOfSubsets(int[] numbers, int sum)
{
int[] dp = new int[sum + 1];
dp[0] = 1;
int currentSum =0;
for (int i = 0; i < numbers.Length; i++)
{
currentSum += numbers[i];
for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--)
dp[j] += dp[j - numbers[i]];
}
return dp[sum];
}
Notes: As number of subsets may have value 2^N it easy may overflows int type.
Algo works only for positive numbers.
Here is a Java Solution:
This is a classical Back tracking problem for finding all possible subsets of the integer array or set that is the input and then filtering those which sum to e given target
import java.util.HashSet;
import java.util.StringTokenizer;
/**
* Created by anirudh on 12/5/15.
*/
public class findSubsetsThatSumToATarget {
/**
* The collection for storing the unique sets that sum to a target.
*/
private static HashSet<String> allSubsets = new HashSet<>();
/**
* The String token
*/
private static final String token = " ";
/**
* The method for finding the subsets that sum to a target.
*
* @param input The input array to be processed for subset with particular sum
* @param target The target sum we are looking for
* @param ramp The Temporary String to be beefed up during recursive iterations(By default value an empty String)
* @param index The index used to traverse the array during recursive calls
*/
public static void findTargetSumSubsets(int[] input, int target, String ramp, int index) {
if(index > (input.length - 1)) {
if(getSum(ramp) == target) {
allSubsets.add(ramp);
}
return;
}
//First recursive call going ahead selecting the int at the currenct index value
findTargetSumSubsets(input, target, ramp + input[index] + token, index + 1);
//Second recursive call going ahead WITHOUT selecting the int at the currenct index value
findTargetSumSubsets(input, target, ramp, index + 1);
}
/**
* A helper Method for calculating the sum from a string of integers
*
* @param intString the string subset
* @return the sum of the string subset
*/
private static int getSum(String intString) {
int sum = 0;
StringTokenizer sTokens = new StringTokenizer(intString, token);
while (sTokens.hasMoreElements()) {
sum += Integer.parseInt((String) sTokens.nextElement());
}
return sum;
}
/**
* Cracking it down here : )
*
* @param args command line arguments.
*/
public static void main(String[] args) {
int [] n = {24, 1, 15, 3, 4, 15, 3};
int counter = 1;
FindSubsetsThatSumToATarget.findTargetSumSubsets(n, 25, "", 0);
for (String str: allSubsets) {
System.out.println(counter + ") " + str);
counter++;
}
}
}
It gives space separated values of the subsets that sum to a target.
Would print out commma separated values for the subsets that sum to 25 in
{24, 1, 15, 3, 4, 15, 3}
1) 24 1
2) 3 4 15 3
3) 15 3 4 3
The same site geeksforgeeks also discusses the solution to output all subsets that sum to a particular value: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/
In your case, instead of the output sets, you just need to count them. Be sure to check the optimized version in the same page, as it is an NP-complete problem.
This question also has been asked and answered before in stackoverflow without mentioning that it's a subset-sum problem: Finding all possible combinations of numbers to reach a given sum
Python function subset that return subset of list that adds up to a particular value
def subset(ln, tar):#ln=Lenght Of String, tar= Target
s=[ int(input('Insert Numeric Value Into List:')) for i in range(ln) ]#Inserting int Values in s of type<list>
if sum(s) < tar:#Sum of List is less than Target Value
return
elif sum(s) == tar:#Sum of list is equal to Target Value i.e for all values combinations
return s
elif tar in s:#Target value present in List i.e for single value
return s[s.index(tar)]
else:#For remaining possibilities i.e for all except( single and all values combinations )
from itertools import combinations# To check all combinations ==> itertools.combinations(list,r) OR return list of all subsets of length r
r=[i+1 for i in range(1,ln-1)]# Taking r as only remaining value combinations, i.e.
# Except( r=1 => for single value combinations AND r=length(list) || r=ln => For all value combinations
lst=list()#For Storing all remaining combinations
for i in range(len(r)):
lst.extend(list( combinations(s,r[i]) ))
for i in range(len(lst)):# To check remaining possibilities
if tar == sum(lst[i]):
return list(lst[i])
subset( int(input('Length of list:')), int(input('Target:')))
RUBY
This code will reject the empty arrays and returns the proper array with values.
def find_sequence(val, num)
b = val.length
(0..b - 1).map {|n| val.uniq.combination(n).each.find_all {|value| value.reduce(:+) == num}}.reject(&:empty?)
end
val = [-10, 1, -1, 2, 0]
num = 2
Output will be [[2],[2,0],[-1,1,2],[-1,1,2,0]]
My backtracking solution :- Sort the array , then apply the backtracking.
void _find(int arr[],int end,vector<int> &v,int start,int target){
if(target==0){
for(int i = 0;i<v.size();i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
else{
for(int i = start;i<=end && target >= arr[i];i++){
v.push_back(arr[i]);
_find(arr,end,v,i+1,target-arr[i]);
v.pop_back();
}
}
}
I have found that so many interviews are asking for this so I implemented a really quite simple and understandable solution. First I generate all the possible combinations, and from there, you can do whatever you want. Check this out:
public static void main(String[] args) {
int[] numbers = new int[]{1, 2, 3, 4, 5};
List<int[]> allPossibleCombinatiosForNumbers = new ArrayList<>();
for (int i = 2; i < numbers.length; i++) {
allPossibleCombinatiosForNumbers.addAll(getCombinationsOfNElements(numbers, i));
}
for (int[] combination : allPossibleCombinatiosForNumbers) {
printArray(combination);
printArrayIfNumbersSumExpectedValue(combination, 6);
}
}
private static List<int[]> getCombinationsOfNElements(int[] numbers, int n) {
int elementsKnown = n - 1;
List<int[]> allCombinationsOfNElements = new ArrayList<>();
for (int i = 0; i < numbers.length - elementsKnown; i++) {
int[] combination = new int[n];
for (int j = 0; j < n; j++) {
combination[j] = numbers[i + j];
}
allCombinationsOfNElements.addAll(generationCombinations(combination, i + elementsKnown, numbers));
}
return allCombinationsOfNElements;
}
private static List<int[]> generationCombinations(int[] knownElements, int index, int[] numbers) {
List<int[]> combinations = new ArrayList<>();
for (int i = index; i < numbers.length; i++) {
int[] combinationComplete = Arrays.copyOf(knownElements, knownElements.length);
combinationComplete[knownElements.length - 1] = numbers[i];
combinations.add(combinationComplete);
}
return combinations;
}
private static void printArray(int[] numbers) {
System.out.println();
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
}
private static void printArrayIfNumbersSumExpectedValue(int[] numbers, int expectedValue) {
int total = 0;
for (int i = 0; i < numbers.length; i++) {
total += numbers[i];
}
if (total == expectedValue) {
System.out.print("\n ----- Here is a combination you are looking for -----");
printArray(numbers);
System.out.print("\n -------------------------------");
}
}
Subset sum problem can be solved in O(sum*n) using dynamic programming. Optimal substructure for subset sum is as follows:
SubsetSum(A, n, sum) = SubsetSum(A, n-1, sum) || SubsetSum(A, n-1, sum-set[n-1])
SubsetSum(A, n, sum) = 0, if sum > 0 and n == 0 SubsetSum(A, n, sum) = 1, if sum == 0
Here A is array of elements, n is the number of elements of array A and sum is the sum of elements in the subset.
Using this dp, you can solve for the number of subsets for the sum.
For getting subset elements, we can use following algorithm:
After filling dp[n][sum] by calling SubsetSum(A, n, sum), we recursively traverse it from dp[n][sum]. For cell being traversed, we store path before reaching it and consider two possibilities for the element.
1) Element is included in current path.
2) Element is not included in current path.
Whenever sum becomes 0, we stop the recursive calls and print current path.
void findAllSubsets(int dp[], int A[], int i, int sum, vector<int>& p) {
if (sum == 0) {
print(p);
return;
}
// If sum can be formed without including current element
if (dp[i-1][sum])
{
// Create a new vector to store new subset
vector<int> b = p;
findAllSubsets(dp, A, i-1, sum, b);
}
// If given sum can be formed after including
// current element.
if (sum >= A[i] && dp[i-1][sum-A[i]])
{
p.push_back(A[i]);
findAllSubsets(dp, A, i-1, sum-A[i], p);
}
}
Here is an efficient solution when there is a large set of inputs (i.e. 25 to 30)
I made efficiency gains in two ways:
This solution works with negative numbers, decimal amounts, and repeated input values. Due to the wonky way that floating point decimal math works in most languages, you will want to keep your input set to only a few decimal places or you may have some unpredictable behavior.
On my old 2012-era desktop computer the given code processes 25 input values in about 0.8 seconds in javascript/node.js, and 3.4 seconds in C#.
let numbers = [-0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51, 0.59, 0.63, 0.79, 0.85,
0.91, 0.99, 1.02, 1.17, 1.25, 1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31];
let target = 24.16;
displaySubsetsThatSumTo(target, numbers);
function displaySubsetsThatSumTo(target, numbers)
{
let wheel = [0];
let resultsCount = 0;
let sum = 0;
const start = new Date();
do {
sum = incrementWheel(0, sum, numbers, wheel);
//Use subtraction comparison due to javascript float imprecision
if (sum != null && Math.abs(target - sum) < 0.000001) {
//Found a subset. Display the result.
console.log(numbers.filter(function(num, index) {
return wheel[index] === 1;
}).join(' + ') + ' = ' + target);
resultsCount++;
}
} while (sum != null);
const end = new Date();
console.log('--------------------------');
console.log(`Processed ${numbers.length} numbers in ${(end - start) / 1000} seconds (${resultsCount} results)`);
}
function incrementWheel(position, sum, numbers, wheel) {
if (position === numbers.length || sum === null) {
return null;
}
wheel[position]++;
if (wheel[position] === 2) {
wheel[position] = 0;
sum -= numbers[position];
if (wheel.length < position + 2) {
wheel.push(0);
}
sum = incrementWheel(position + 1, sum, numbers, wheel);
}
else {
sum += numbers[position];
}
return sum;
}
-----------------------------------------------------------------
Alternate, more efficient version using Gray Code binary counting
technique as suggested in comment
-----------------------------------------------------------------
const numbers = [-0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51,
0.59, 0.63, 0.79, 0.85, 0.91, 0.99, 1.02, 1.17, 1.25,
1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31];
const target = 24.16;
displaySubsetsThatSumTo(target, numbers);
function displaySubsetsThatSumTo(target, numbers)
{
let resultsCount = 0;
let sum = 0;
let wheel = []; //binary counter
let changeEvery = []; //how often each binary digit flips
let nextChange = []; //when each binary digit will next flip
for(let i = 0; i < numbers.length; i++) {
//Initialize wheel and wheel-update data. Using Gray Code binary counting technique,
// whereby only one binary digit in the wheel changes on each iteration. Then only
// a single sum operation is required each iteration.
wheel.push(0);
changeEvery.push(2 ** (numbers.length - i));
nextChange.push(2 ** (numbers.length - i - 1));
}
const start = new Date();
const numIterations = 2 ** numbers.length;
for (counter = 1; counter < numIterations; counter++) {
for (let i = nextChange.length - 1; i >= 0; i--) {
if(nextChange[i] === counter) {
nextChange[i] += changeEvery[i];
if (wheel[i] === 1) {
wheel[i] = 0;
sum -= numbers[i];
}
else {
wheel[i] = 1;
sum += numbers[i];
}
break;
}
}
//Use subtraction comparison due to javascript float imprecision
if (Math.abs(target - sum) < 0.000001) {
//Found a subset. Display the result.
console.log(numbers.filter((num, index) => wheel[index] === 1)
.join(' + ') + ' = ' + target);
resultsCount++;
}
}
const end = new Date();
console.log('--------------------------');
console.log(`Processed ${numbers.length} numbers in ${(end - start) / 1000} seconds (${resultsCount} results)`);
}
public class Program
{
static void Main(string[] args)
{
double[] numbers = { -0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51, 0.59, 0.63, 0.79, 0.85,
0.91, 0.99, 1.02, 1.17, 1.25, 1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31 };
double target = 24.16;
DisplaySubsetsThatSumTo(target, numbers);
}
private static void DisplaySubsetsThatSumTo(double Target, double[] numbers)
{
var stopwatch = new System.Diagnostics.Stopwatch();
bool[] wheel = new bool[numbers.Length];
int resultsCount = 0;
double? sum = 0;
stopwatch.Start();
do
{
sum = IncrementWheel(0, sum, numbers, wheel);
//Use subtraction comparison due to double type imprecision
if (sum.HasValue && Math.Abs(sum.Value - Target) < 0.000001F)
{
//Found a subset. Display the result.
Console.WriteLine(string.Join(" + ", numbers.Where((n, idx) => wheel[idx])) + " = " + Target);
resultsCount++;
}
} while (sum != null);
stopwatch.Stop();
Console.WriteLine("--------------------------");
Console.WriteLine($"Processed {numbers.Length} numbers in {stopwatch.ElapsedMilliseconds / 1000.0} seconds ({resultsCount} results). Press any key to exit.");
Console.ReadKey();
}
private static double? IncrementWheel(int Position, double? Sum, double[] numbers, bool[] wheel)
{
if (Position == numbers.Length || !Sum.HasValue)
{
return null;
}
wheel[Position] = !wheel[Position];
if (!wheel[Position])
{
Sum -= numbers[Position];
Sum = IncrementWheel(Position + 1, Sum, numbers, wheel);
}
else
{
Sum += numbers[Position];
}
return Sum;
}
}
-0.35 + 0.23 + 0.36 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
0.23 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.47 + 0.23 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.19 + 0.36 + 0.51 + 0.59 + 0.63 + 0.79 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.47 + -0.19 + 0.36 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
0.23 + 0.47 + 0.51 + 0.63 + 0.85 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
--------------------------
Processed 25 numbers in 0.823 seconds (6 results)
Following solution also provide array of subset which provide specific sum (here sum = 9)
array = [1, 3, 4, 2, 7, 8, 9]
(0..array.size).map { |i| array.combination(i).to_a.select { |a| a.sum == 9 } }.flatten(1)
return array of subsets which return sum of 9
=> [[9], [1, 8], [2, 7], [3, 4, 2]]
I have solved this by java. This solution is quite simple.
import java.util.*;
public class Recursion {
static void sum(int[] arr, int i, int sum, int target, String s)
{
for(int j = i+1; j<arr.length; j++){
if(sum+arr[j] == target){
System.out.println(s+" "+String.valueOf(arr[j]));
}else{
sum(arr, j, sum+arr[j], target, s+" "+String.valueOf(arr[j]));
}
}
}
public static void main(String[] args)
{
int[] numbers = {6,3,8,10,1};
for(int i =0; i<numbers.length; i++){
sum(numbers, i, numbers[i], 18, String.valueOf(numbers[i]));
}
}
}
While it is straightforward to find if their is a subset or not that sums to the target, implementation gets tricky when you need to keep track of the partial subsets under consideration.
If you use a linked list, a hash set or any another generic collection, you would be tempted to add an item to this collection before the call that includes the item, and then remove it before the call that excludes the item. This does not work as expected, as the stack frames in which the add will occur is not the same as the one in which remove will occur.
Solution is to use a string to keep track of the sequence. Appends to the string can be done inline in the function call; thereby maintaining the same stack frame and your answer would then conform beautifully to the original hasSubSetSum recursive structure.
import java.util.ArrayList;
public class Solution {
public static boolean hasSubSet(int [] A, int target) {
ArrayList<String> subsets = new ArrayList<>();
helper(A, target, 0, 0, subsets, "");
// Printing the contents of subsets is straightforward
return !subsets.isEmpty();
}
private static void helper(int[] A, int target, int sumSoFar, int i, ArrayList<String> subsets, String curr) {
if(i == A.length) {
if(sumSoFar == target) {
subsets.add(curr);
}
return;
}
helper(A, target, sumSoFar, i+1, subsets, curr);
helper(A, target, sumSoFar + A[i], i+1, subsets, curr + A[i]);
}
public static void main(String [] args) {
System.out.println(hasSubSet(new int[] {1,2,4,5,6}, 8));
}
}
I used Dynamic Programming & Memoization to find count of subsets from a set having a particular total. The code below code is in java. Have included the comments to explain the code intentions -
package com.company.dynamicProgramming;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class FindSumInSubSet {
public static void main(String...args){
int[] arr = {3, 2, 4, 6, 10};
int total = 16;
// Challenge is to find the subsets of numbers total 6 in above super set (represented as array)
// In general - Write a code to count subset of elements totalling m(6 above) in given set of n(9 as array size above) elements
Map<Entry, Integer> memoMap = new HashMap<>();
Entry entry = new Entry(total, arr.length-1);
int count = countSubSetForSum(arr, entry, memoMap);
System.out.format("In set of %d elements, the number of subsets having total=%d is %d %n", arr.length,total, count);
}
static int countSubSetForSum(int[] arr, Entry entry, Map<Entry, Integer> memoMap){
int total = entry.getTotal();
int i = entry.getI();
if (total == 0){ // means element was equal in previous recursion
return 1;
}else if(total < 0){ // means element was less in previous recursion i.e. not equal
return 0;
}else if (i < 0){ // means arr was finished previous recursion
return 0;
}else if (arr[i] > total){ // means element is greater than total
// i.e. leave that element and look further sets excluding this element
return getCountForIthAndTotal(arr, new Entry( total, i-1), memoMap);
}else{ // means element is less than total i.e. 2 possibilities :
// 1st - look further sets including this element
// 2nd - look further sets excluding this element
return getCountForIthAndTotal(arr, new Entry( total-arr[i], i-1), memoMap) +
getCountForIthAndTotal(arr, new Entry( total, i-1), memoMap);
}
}
static int getCountForIthAndTotal(int[] arr, Entry entry, Map<Entry, Integer> memoMap){
if (memoMap.containsKey(entry)){ //look up in has table if we already calculated particular total for ith subset..
return memoMap.get(entry); //This is nothing but using memoization that reduce the entire below code i.e. further recursion -
}else {
int count = countSubSetForSum(arr, entry, memoMap); //Recursion
memoMap.put(entry, count); //Build memoization
return count;
}
}
//Just Data Structure for Key in HashMap (memoMaP)... intent to include particular total for ith element's subset.
static class Entry {
int total;
int i;
public Entry(int total, int i) {
this.total = total;
this.i = i;
}
public int getTotal() {
return total;
}
public int getI() {
return i;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Entry entry = (Entry) o;
return total == entry.total &&
i == entry.i;
}
@Override
public int hashCode() {
return Objects.hash(total, i);
}
}
}
When i ran this the out put is :
In set of 5 elements, the number of subsets having total=16 is 2
Process finished with exit code 0
Source: Stackoverflow.com