Continuous Subsequence Which Sums Up to a Target

Given a set of integers, find a distinct sum that can be generated from the subsets of the given sets and print them in increasing order. It is given that sum of array elements is small.

Examples:

Input  : arr[] = {1, 2, 3} Output : 0 1 2 3 4 5 6 Distinct subsets of given set are {}, {1}, {2}, {3}, {1,2}, {2,3},  {1,3} and {1,2,3}.  Sums of these subsets are 0, 1, 2, 3, 3, 5, 4, 6 After removing duplicates, we get 0, 1, 2, 3, 4, 5, 6    Input : arr[] = {2, 3, 4, 5, 6} Output : 0 2 3 4 5 6 7 8 9 10 11 12           13 14 15 16 17 18 20  Input : arr[] = {20, 30, 50} Output : 0 20 30 50 70 80 100

The naive solution for this problem is to generate all the subsets, store their sums in a hash set and finally print all keys from the hash set.

C++

#include<bits/stdc++.h>

using namespace std;

void distSumRec( int arr[], int n, int sum,

int currindex, unordered_set< int > &s)

{

if (currindex > n)

return ;

if (currindex == n)

{

s.insert(sum);

return ;

}

distSumRec(arr, n, sum + arr[currindex],

currindex+1, s);

distSumRec(arr, n, sum, currindex+1, s);

}

void printDistSum( int arr[], int n)

{

unordered_set< int > s;

distSumRec(arr, n, 0, 0, s);

for ( auto i=s.begin(); i!=s.end(); i++)

cout << *i << " " ;

}

int main()

{

int arr[] = {2, 3, 4, 5, 6};

int n = sizeof (arr)/ sizeof (arr[0]);

printDistSum(arr, n);

return 0;

}

Java

import java.io.*;

import java.util.*;

class GFG

{

static void distSumRec( int arr[], int n, int sum,

int currindex, HashSet<Integer> s)

{

if (currindex > n)

return ;

if (currindex == n) {

s.add(sum);

return ;

}

distSumRec(arr, n, sum + arr[currindex],

currindex + 1 , s);

distSumRec(arr, n, sum, currindex + 1 , s);

}

static void printDistSum( int arr[], int n)

{

HashSet<Integer> s = new HashSet<>();

distSumRec(arr, n, 0 , 0 , s);

for ( int i : s)

System.out.print(i + " " );

}

public static void main(String[] args)

{

int arr[] = { 2 , 3 , 4 , 5 , 6 };

int n = arr.length;

printDistSum(arr, n);

}

}

Python3

def distSumRec(arr, n, sum , currindex, s):

if (currindex > n):

return

if (currindex = = n):

s.add( sum )

return

distSumRec(arr, n, sum + arr[currindex], currindex + 1 , s)

distSumRec(arr, n, sum , currindex + 1 , s)

def printDistSum(arr,n):

s = set ()

distSumRec(arr, n, 0 , 0 , s)

for i in s:

print (i,end = " " )

if __name__ = = '__main__' :

arr = [ 2 , 3 , 4 , 5 , 6 ]

n = len (arr)

printDistSum(arr, n)

C#

using System;

using System.Collections.Generic;

class GFG

{

static void distSumRec( int []arr, int n, int sum,

int currindex, HashSet< int > s)

{

if (currindex > n)

return ;

if (currindex == n)

{

s.Add(sum);

return ;

}

distSumRec(arr, n, sum + arr[currindex],

currindex + 1, s);

distSumRec(arr, n, sum, currindex + 1, s);

}

static void printDistSum( int []arr, int n)

{

HashSet< int > s = new HashSet< int >();

distSumRec(arr, n, 0, 0, s);

foreach ( int i in s)

Console.Write(i + " " );

}

public static void Main()

{

int []arr = { 2, 3, 4, 5, 6 };

int n = arr.Length;

printDistSum(arr, n);

}

}

Javascript

<script>

function distSumRec(arr,n,sum,currindex,s)

{

if (currindex > n)

return ;

if (currindex == n) {

s.add(sum);

return ;

}

distSumRec(arr, n, sum + arr[currindex],

currindex + 1, s);

distSumRec(arr, n, sum, currindex + 1, s);

}

function printDistSum(arr,n)

{

let s= new Set();

distSumRec(arr, n, 0, 0, s);

let s1=[...s]

s1.sort( function (a,b){ return a-b;})

for (let [key, value] of s1.entries())

document.write(value + " " );

}

let arr=[2, 3, 4, 5, 6 ];

let n = arr.length;

printDistSum(arr, n);

</script>

Output:

0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20

The time complexity of the above naive recursive approach is O(2ⁿ).

The time complexity of the above problem can be improved using Dynamic Programming, especially when the sum of given elements is small. We can make a dp table with rows containing the size of the array and the size of the column will be the sum of all the elements in the array.

C++

#include<bits/stdc++.h>

using namespace std;

void printDistSum( int arr[], int n)

{

int sum = 0;

for ( int i=0; i<n; i++)

sum += arr[i];

bool dp[n+1][sum+1];

memset (dp, 0, sizeof (dp));

for ( int i=0; i<=n; i++)

dp[i][0] = true ;

for ( int i=1; i<=n; i++)

{

dp[i][arr[i-1]] = true ;

for ( int j=1; j<=sum; j++)

{

if (dp[i-1][j] == true )

{

dp[i][j] = true ;

dp[i][j + arr[i-1]] = true ;

}

}

}

for ( int j=0; j<=sum; j++)

if (dp[n][j]== true )

cout << j << " " ;

}

int main()

{

int arr[] = {2, 3, 4, 5, 6};

int n = sizeof (arr)/ sizeof (arr[0]);

printDistSum(arr, n);

return 0;

}

Java

import java.io.*;

import java.util.*;

class GFG {

static void printDistSum( int arr[], int n)

{

int sum = 0 ;

for ( int i = 0 ; i < n; i++)

sum += arr[i];

boolean [][] dp = new boolean [n + 1 ][sum + 1 ];

for ( int i = 0 ; i <= n; i++)

dp[i][ 0 ] = true ;

for ( int i = 1 ; i <= n; i++)

{

dp[i][arr[i - 1 ]] = true ;

for ( int j = 1 ; j <= sum; j++)

{

if (dp[i - 1 ][j] == true )

{

dp[i][j] = true ;

dp[i][j + arr[i - 1 ]] = true ;

}

}

}

for ( int j = 0 ; j <= sum; j++)

if (dp[n][j] == true )

System.out.print(j + " " );

}

public static void main(String[] args)

{

int arr[] = { 2 , 3 , 4 , 5 , 6 };

int n = arr.length;

printDistSum(arr, n);

}

}

Python3

def printDistSum(arr, n):

Sum = sum (arr)

dp = [[ False for i in range ( Sum + 1 )]

for i in range (n + 1 )]

for i in range (n + 1 ):

dp[i][ 0 ] = True

for i in range ( 1 , n + 1 ):

dp[i][arr[i - 1 ]] = True

for j in range ( 1 , Sum + 1 ):

if (dp[i - 1 ][j] = = True ):

dp[i][j] = True

dp[i][j + arr[i - 1 ]] = True

for j in range ( Sum + 1 ):

if (dp[n][j] = = True ):

print (j, end = " " )

arr = [ 2 , 3 , 4 , 5 , 6 ]

n = len (arr)

printDistSum(arr, n)

C#

using System;

class GFG {

static void printDistSum( int []arr, int n)

{

int sum = 0;

for ( int i = 0; i < n; i++)

sum += arr[i];

bool [,]dp = new bool [n + 1,sum + 1];

for ( int i = 0; i <= n; i++)

dp[i,0] = true ;

for ( int i = 1; i <= n; i++)

{

dp[i,arr[i - 1]] = true ;

for ( int j = 1; j <= sum; j++)

{

if (dp[i - 1,j] == true )

{

dp[i,j] = true ;

dp[i,j + arr[i - 1]] = true ;

}

}

}

for ( int j = 0; j <= sum; j++)

if (dp[n,j] == true )

Console.Write(j + " " );

}

public static void Main()

{

int []arr = { 2, 3, 4, 5, 6 };

int n = arr.Length;

printDistSum(arr, n);

}

}

Javascript

<script>

function printDistSum(arr, n)

{

var sum = 0;

for ( var i = 0; i < n; i++)

sum += arr[i];

var dp = Array.from(

Array(n + 1), () => Array(sum + 1).fill(0));

for ( var i = 0; i <= n; i++)

dp[i][0] = true ;

for ( var i = 1; i <= n; i++)

{

dp[i][arr[i - 1]] = true ;

for ( var j = 1; j <= sum; j++)

{

if (dp[i - 1][j] == true )

{

dp[i][j] = true ;

dp[i][j + arr[i - 1]] = true ;

}

}

}

for ( var j = 0; j <= sum; j++)

if (dp[n][j] == true )

document.write(j + " " );

}

var arr = [ 2, 3, 4, 5, 6 ];

var n = arr.length;

printDistSum(arr, n);

</script>

Output:

0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20

Time complexity of the above approach is O(n*sum) where n is the size of the array and sum is the sum of all the integers in the array.

Optimized Bit-set Approach

dp = dp | dp << a[i]

Above Code snippet does the same as naive solution, where dp is a bit mask (we'll use bit-set). Lets see how:

1. dp → all the sums which were produced before element a[i]
2. dp << a[i] → shifting all the sums by a[i], i.e. adding a[i] to all the sums.
   1. For example, Suppose initially the bit-mask was 000010100 meaning we could generate only 2 and 4 (count from right).
   2. Now if we get a element 3, we could make 5 and 7 as well by adding to 2 and 4 respectively.
   3. This can be denoted by 010100000 which is equivalent to (000010100) << 3
3. dp | (dp << a[i]) → 000010100 | 010100000 = 010110100 This is union of above two sums representing which sums are possible, namely 2, 4, 5 and 7.

bitset optimized knapsack

C++

#include <bits/stdc++.h>

using namespace std;

int main()

{

vector< int > a = { 2, 3, 4, 5, 6 };

int n = a.size();

const int mx = 40;

bitset<mx> dp;

dp[0] = 1;

for ( int i = 0; i < n; ++i) {

dp |= dp << a[i];

}

for ( int i = 0; i <= mx; i++) {

if (dp[i] == 1)

cout << i << " " ;

}

}

Output

0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20          

Time Complexity also seems to be O(N * S). Because if we would have used a array instead of bitset the shifting would have taken linear time O(S). However the shift (and almost all) operation on bitset takes O(S / W) time. Where W is the word size of the system, Usually its 32 bit or 64 bit. Thus the final time complexity becomes O(N * S / W)

Some Important Points:

1. The size of bitset must be a constant, this sometimes is a drawback as we might waste some space.
2. Bitset can be thought of a array where every element takes care of W elements. For example 010110100 is equivalent to {2, 6, 4} in a hypothetical system with word size W = 3.
3. Bitset optimized knapsack solution reduced the time complexity by a factor of W which sometimes is just enough to get AC.

This article is contributed by Karan Goyal. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

dodgshunhillow.blogspot.com

Source: https://www.geeksforgeeks.org/find-distinct-subset-subsequence-sums-array/

Share this post