Posted on by Kalkicode
Code Stack

# Find all distinct subsets of given sum

The problem is to find all distinct subsets of a given sum. A subset is a collection of elements from a given set, and the sum of elements in the subset should be equal to the given sum.

## Problem Statement

Given a sum, find all distinct subsets of the numbers that sum up to the given sum.

## Example

Consider the following example:

Input:

``sum = 5``

Output:

``````Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]
``````

Explanation:

• The first subset `[ 1 1 1 1 1 ]` consists of five elements, each equal to 1, and the sum of the elements is 5.
• The second subset `[ 1 1 1 2 ]` consists of four elements, three 1's and one 2, and the sum of the elements is 5.
• The third subset `[ 1 1 3 ]` consists of three elements, two 1's and one 3, and the sum of the elements is 5.
• The fourth subset `[ 1 2 2 ]` consists of three elements, one 1 and two 2's, and the sum of the elements is 5.
• The fifth subset `[ 1 4 ]` consists of two elements, one 1 and one 4, and the sum of the elements is 5.
• The sixth subset `[ 2 3 ]` consists of two elements, one 2 and one 3, and the sum of the elements is 5.
• The seventh subset `[ 5 ]` consists of one element, and the sum of the element is 5.

## Idea to Solve the Problem

To find all distinct subsets of a given sum, we can use backtracking. We start with an empty stack, and for each number from 1 to the given sum, we add it to the stack and recursively find the subsets for the remaining sum. If the sum becomes 0, we have found a valid subset, and we print the elements in the stack. We then backtrack by removing the last element from the stack and try the next number. This way, we find all possible subsets that sum up to the given sum.

## Pseudocode

``````
Define a custom stack class StackNode
element
next

Define a custom stack class MyStack
top
size
push(element)
pop()
peek()
isEmpty()

Define a class SubSetSum
stack

Constructor SubSetSum()
Create a new instance of MyStack and assign it to stack

show(top)
If top is null, return
Get the element of top
Recursively call show with top.next
Print the element

subset(location, sum)
If sum is 0
Print the subset by calling show function on stack.top
For i from location to sum
Push i onto the stack
Call subset with i and sum - i
Pop the top element from the stack

findSubset(sum)
If sum is less than or equal to 0, return
Print "Subset of sum" and the value of sum
Call the subset function with location = 1 and the given sum

Main function
Create an instance of SubSetSum called task

``````

## Algorithm

1. Define a custom class `StackNode` to represent a node in the stack. It will have two fields: `element` to store the value and `next` to point to the next node in the stack.
2. Define another custom class `MyStack` to represent the stack. It will have two fields: `top` to point to the top node in the stack and `size` to store the number of elements in the stack. It will also have functions `push`, `pop`, `peek`, and `isEmpty`.
3. Define a class `SubSetSum` with a field `stack` of type `MyStack`. In the constructor, initialize `stack` to a new instance of `MyStack`.
4. Define a function `show` that takes a node `top` as a parameter and recursively prints the elements of the stack starting from `top`.
5. Define a function `subset` that takes two parameters: `location` and `sum`. This function will find all subsets of the given `sum` starting from the `location` element.
6. If `sum` is 0, print the current subset by calling the `show` function on `stack.top`.
7. For each number `i` from `location` to `sum`, do the following:
• Push `i` onto the stack.
• Call the `subset` function with `i` as the new `location` and `sum - i` as the new `sum`.
• Pop the top element from the stack to backtrack and try the next number.
8. Define a function `findSubset` that takes a parameter `sum` and finds all subsets of the given `sum`.
9. If `sum` is less than or equal to 0, return.
10. Print "Subset of sum" and the value of `sum`.
11. Call the `subset` function with `location = 1` and the given `sum`.
12. In the `main` function, create an instance of `SubSetSum` called `task`.
13. Call `task.findSubset(5)` and `task.findSubset(10)` to find all subsets of sum 5 and 10, respectively.

## Code Solution

``````// C program
// Find all distinct subsets of given sum
#include <stdio.h>
#include <stdlib.h>

// Define stack
struct MyStack
{
int element;
struct MyStack *next;
};
// Add new element into stack
void push(struct MyStack **top, int data)
{
//Make a new node
struct MyStack *new_node = (struct MyStack *) malloc(sizeof(struct MyStack));
if (new_node != NULL)
{
//Set node values
new_node->element = data;
new_node->next = *top;*top = new_node;
}
else
{
printf("Memory Overflow\n");
}
}
// Remove top element of stack
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *temp = *top;*top = temp->next;
free(temp);
temp = NULL;
}
}

// Display stack elements in reverse order
void show(struct MyStack *top)
{
if (top == NULL)
{
return;
}
// Get top element
int element = top->element;
// next top
show(top->next);
// Display element
printf("  %d", element);
}
// Finding the all distinct subsets of given sum
void subset(struct MyStack **top, int location, int sum)
{
if (sum == 0)
{
// Display subset
printf(" [");
show( *top);
printf("  ]\n");
}
for (int i = location; i <= sum; i++)
{
push(top, i);
subset(top, i, sum - i);
// Remove top element of stack
pop(top);
}
}
// Handles the request to find subset Sum
void findSubset(int sum)
{
if (sum <= 0)
{
return;
}
// Define a stack
struct MyStack *top = NULL;
printf("\n Subset of sum %d \n", sum);
subset( &top, 1, sum);
}
int main()
{
// Test case
findSubset(5);
findSubset(10);
return 0;
}``````

#### Output

`````` Subset of sum 5
[  1  1  1  1  1  ]
[  1  1  1  2  ]
[  1  1  3  ]
[  1  2  2  ]
[  1  4  ]
[  2  3  ]
[  5  ]

Subset of sum 10
[  1  1  1  1  1  1  1  1  1  1  ]
[  1  1  1  1  1  1  1  1  2  ]
[  1  1  1  1  1  1  1  3  ]
[  1  1  1  1  1  1  2  2  ]
[  1  1  1  1  1  1  4  ]
[  1  1  1  1  1  2  3  ]
[  1  1  1  1  1  5  ]
[  1  1  1  1  2  2  2  ]
[  1  1  1  1  2  4  ]
[  1  1  1  1  3  3  ]
[  1  1  1  1  6  ]
[  1  1  1  2  2  3  ]
[  1  1  1  2  5  ]
[  1  1  1  3  4  ]
[  1  1  1  7  ]
[  1  1  2  2  2  2  ]
[  1  1  2  2  4  ]
[  1  1  2  3  3  ]
[  1  1  2  6  ]
[  1  1  3  5  ]
[  1  1  4  4  ]
[  1  1  8  ]
[  1  2  2  2  3  ]
[  1  2  2  5  ]
[  1  2  3  4  ]
[  1  2  7  ]
[  1  3  3  3  ]
[  1  3  6  ]
[  1  4  5  ]
[  1  9  ]
[  2  2  2  2  2  ]
[  2  2  2  4  ]
[  2  2  3  3  ]
[  2  2  6  ]
[  2  3  5  ]
[  2  4  4  ]
[  2  8  ]
[  3  3  4  ]
[  3  7  ]
[  4  6  ]
[  5  5  ]
[  10  ]``````
``````/*
Java Program for
Find all distinct subsets of given sum
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
return this.top.element;
}
}
public class SubSetSum
{
public MyStack stack;
public SubSetSum()
{
this.stack = new MyStack();
}
public void show(StackNode top)
{
if (top == null)
{
return;
}
// Get top element
int element = top.element;
// next top
show(top.next);
// Display element
System.out.print(" " + element);
}
// Finding the all distinct subsets of given sum
public void subset(int location, int sum)
{
if (sum == 0)
{
// Display subset
System.out.print(" [");
show(this.stack.top);
System.out.print(" ]\n");
}
for (int i = location; i <= sum; i++)
{
this.stack.push(i);
subset(i, sum - i);
// Remove top element of stack
this.stack.pop();
}
}
// Handles the request to find subset Sum
public void findSubset(int sum)
{
if (sum <= 0)
{
return;
}
System.out.print("\n Subset of sum " + sum + " \n");
subset(1, sum);
}
public static void main(String[] args)
{
// Test case
}
}``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program for
Find all distinct subsets of given sum
*/

// Define stack node
class StackNode
{
public:
int element;
StackNode *next;
StackNode(int element, StackNode *next)
{
this->element = element;
this->next = next;
}
};
// Define a custom stack
class MyStack
{
public:
StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
delete temp;
// remove previous top
temp = NULL;
this->size--;
}
}
int peek()
{
return this->top->element;
}
};
class SubSetSum
{
public:
MyStack *stack;
SubSetSum()
{
this->stack = new MyStack();
}
void show(StackNode *top)
{
if (top == NULL)
{
return;
}
// Get top element
int element = top->element;
// next top
this->show(top->next);
// Display element
cout << " " << element;
}
// Finding the all distinct subsets of given sum
void subset(int location, int sum)
{
if (sum == 0)
{
// Display subset
cout << " [";
this->show(this->stack->top);
cout << " ]\n";
}
for (int i = location; i <= sum; i++)
{
this->stack->push(i);
this->subset(i, sum - i);
// Remove top element of stack
this->stack->pop();
}
}
// Handles the request to find subset Sum
void findSubset(int sum)
{
if (sum <= 0)
{
return;
}
cout << "\n Subset of sum " << sum << " \n";
this->subset(1, sum);
}
};
int main()
{
// Test case
return 0;
}``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]``````
``````// Include namespace system
using System;
/*
C# Program for
Find all distinct subsets of given sum
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
return this.top.element;
}
}
public class SubSetSum
{
public MyStack stack;
public SubSetSum()
{
this.stack = new MyStack();
}
public void show(StackNode top)
{
if (top == null)
{
return;
}
// Get top element
int element = top.element;
// next top
show(top.next);
// Display element
Console.Write(" " + element);
}
// Finding the all distinct subsets of given sum
public void subset(int location, int sum)
{
if (sum == 0)
{
// Display subset
Console.Write(" [");
show(this.stack.top);
Console.Write(" ]\n");
}
for (int i = location; i <= sum; i++)
{
this.stack.push(i);
subset(i, sum - i);
// Remove top element of stack
this.stack.pop();
}
}
// Handles the request to find subset Sum
public void findSubset(int sum)
{
if (sum <= 0)
{
return;
}
Console.Write("\n Subset of sum " + sum + " \n");
subset(1, sum);
}
public static void Main(String[] args)
{
// Test case
}
}``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]``````
``````<?php
/*
Php Program for
Find all distinct subsets of given sum
*/
// Define stack node
class StackNode
{
public \$element;
public \$next;

function __construct(\$element, \$next)
{
\$this->element = \$element;
\$this->next = \$next;
}
}
// Define a custom stack
class MyStack
{
public \$top;
public \$size;

function __construct()
{
//Set node values
\$this->top = null;
\$this->size = 0;
}
// Add node at the top of stack
public	function push(\$element)
{
\$this->top = new StackNode(\$element, \$this->top);
\$this->size++;
}
public	function isEmpty()
{
if (\$this->size > 0 && \$this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public	function pop()
{
if (\$this->size > 0 && \$this->top != null)
{
\$temp = \$this->top;
// Change top element of stack
\$this->top = \$temp->next;
// remove previous top
\$temp = null;
\$this->size--;
}
}
public	function peek()
{
return \$this->top->element;
}
}
class SubSetSum
{
public \$stack;

function __construct()
{
\$this->stack = new MyStack();
}
public	function show(\$top)
{
if (\$top == null)
{
return;
}
// Get top element
\$element = \$top->element;
// next top
\$this->show(\$top->next);
// Display element
echo " ". \$element;
}
// Finding the all distinct subsets of given sum
public	function subset(\$location, \$sum)
{
if (\$sum == 0)
{
// Display subset
echo " [";
\$this->show(\$this->stack->top);
echo " ]\n";
}
for (\$i = \$location; \$i <= \$sum; \$i++)
{
\$this->stack->push(\$i);
\$this->subset(\$i, \$sum - \$i);
// Remove top element of stack
\$this->stack->pop();
}
}
// Handles the request to find subset Sum
public	function findSubset(\$sum)
{
if (\$sum <= 0)
{
return;
}
echo "\n Subset of sum ". \$sum ." \n";
\$this->subset(1, \$sum);
}
}

function main()
{
// Test case
}
main();``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]``````
``````/*
Node Js Program for
Find all distinct subsets of given sum
*/
// Define stack node
class StackNode
{
constructor(element, next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
peek()
{
return this.top.element;
}
}
class SubSetSum
{
constructor()
{
this.stack = new MyStack();
}
show(top)
{
if (top == null)
{
return;
}
// Get top element
var element = top.element;
// next top
this.show(top.next);
// Display element
process.stdout.write(" " + element);
}
// Finding the all distinct subsets of given sum
subset(location, sum)
{
if (sum == 0)
{
// Display subset
process.stdout.write(" [");
this.show(this.stack.top);
process.stdout.write(" ]\n");
}
for (var i = location; i <= sum; i++)
{
this.stack.push(i);
this.subset(i, sum - i);
// Remove top element of stack
this.stack.pop();
}
}
// Handles the request to find subset Sum
findSubset(sum)
{
if (sum <= 0)
{
return;
}
process.stdout.write("\n Subset of sum " + sum + " \n");
this.subset(1, sum);
}
}

function main()
{
// Test case
}
main();``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]``````
``````#    Python 3 Program for
#    Find all distinct subsets of given sum

#  Define stack node
class StackNode :

def __init__(self, element, top) :
self.element = element
self.next = top

#  Define a custom stack
class MyStack :

def __init__(self) :
# Set node values
self.top = None
self.size = 0

#  Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1

def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True

#  Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = None
self.size -= 1

def peek(self) :
return self.top.element

class SubSetSum :

def __init__(self) :
self.stack = MyStack()

def show(self, top) :
if (top == None) :
return

#  Get top element
element = top.element
#  next top
self.show(top.next)
#  Display element
print(" ", element, end = "")

#  Finding the all distinct subsets of given sum
def subset(self, location, sum) :
if (sum == 0) :
#  Display subset
print(" [", end = "")
self.show(self.stack.top)
print(" ]")

i = location
while (i <= sum) :
self.stack.push(i)
self.subset(i, sum - i)
#  Remove top element of stack
self.stack.pop()
i += 1

#  Handles the request to find subset Sum
def findSubset(self, sum) :
if (sum <= 0) :
return

print("\n Subset of sum ", sum ," ")
self.subset(1, sum)

def main() :
#  Test case

if __name__ == "__main__": main()``````

#### Output

`````` Subset of sum  5
[  1  1  1  1  1 ]
[  1  1  1  2 ]
[  1  1  3 ]
[  1  2  2 ]
[  1  4 ]
[  2  3 ]
[  5 ]

Subset of sum  10
[  1  1  1  1  1  1  1  1  1  1 ]
[  1  1  1  1  1  1  1  1  2 ]
[  1  1  1  1  1  1  1  3 ]
[  1  1  1  1  1  1  2  2 ]
[  1  1  1  1  1  1  4 ]
[  1  1  1  1  1  2  3 ]
[  1  1  1  1  1  5 ]
[  1  1  1  1  2  2  2 ]
[  1  1  1  1  2  4 ]
[  1  1  1  1  3  3 ]
[  1  1  1  1  6 ]
[  1  1  1  2  2  3 ]
[  1  1  1  2  5 ]
[  1  1  1  3  4 ]
[  1  1  1  7 ]
[  1  1  2  2  2  2 ]
[  1  1  2  2  4 ]
[  1  1  2  3  3 ]
[  1  1  2  6 ]
[  1  1  3  5 ]
[  1  1  4  4 ]
[  1  1  8 ]
[  1  2  2  2  3 ]
[  1  2  2  5 ]
[  1  2  3  4 ]
[  1  2  7 ]
[  1  3  3  3 ]
[  1  3  6 ]
[  1  4  5 ]
[  1  9 ]
[  2  2  2  2  2 ]
[  2  2  2  4 ]
[  2  2  3  3 ]
[  2  2  6 ]
[  2  3  5 ]
[  2  4  4 ]
[  2  8 ]
[  3  3  4 ]
[  3  7 ]
[  4  6 ]
[  5  5 ]
[  10 ]``````
``````#    Ruby Program for
#    Find all distinct subsets of given sum

#  Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_accessor :element, :next

def initialize(element, top)
self.element = element
self.next = top
end

end

#  Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top, :size

def initialize()
# Set node values
self.top = nil
self.size = 0
end

#  Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end

def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end

end

#  Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = nil
self.size -= 1
end

end

def peek()
return self.top.element
end

end

class SubSetSum
# Define the accessor and reader of class SubSetSum
attr_accessor :stack

def initialize()
self.stack = MyStack.new()
end

def show(top)
if (top == nil)
return
end

#  Get top element
element = top.element
#  next top
self.show(top.next)
#  Display element
print(" ", element)
end

#  Finding the all distinct subsets of given sum
def subset(location, sum)
if (sum == 0)
#  Display subset
print(" [")
self.show(self.stack.top)
print(" ]\n")
end

i = location
while (i <= sum)
self.stack.push(i)
self.subset(i, sum - i)
#  Remove top element of stack
self.stack.pop()
i += 1
end

end

#  Handles the request to find subset Sum
def findSubset(sum)
if (sum <= 0)
return
end

print("\n Subset of sum ", sum ," \n")
self.subset(1, sum)
end

end

def main()
#  Test case
end

main()``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]
``````
``````/*
Scala Program for
Find all distinct subsets of given sum
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
def peek(): Int = {
return this.top.element;
}
}
class SubSetSum(var stack: MyStack)
{
def this()
{
this(new MyStack());
}
def show(top: StackNode): Unit = {
if (top == null)
{
return;
}
// Get top element
var element: Int = top.element;
// next top
this.show(top.next);
// Display element
print(" " + element);
}
// Finding the all distinct subsets of given sum
def subset(location: Int, sum: Int): Unit = {
if (sum == 0)
{
// Display subset
print(" [");
this.show(this.stack.top);
print(" ]\n");
}
var i: Int = location;
while (i <= sum)
{
this.stack.push(i);
this.subset(i, sum - i);
// Remove top element of stack
this.stack.pop();
i += 1;
}
}
// Handles the request to find subset Sum
def findSubset(sum: Int): Unit = {
if (sum <= 0)
{
return;
}
print("\n Subset of sum " + sum + " \n");
this.subset(1, sum);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubSetSum = new SubSetSum();
// Test case
}
}``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]``````
``````/*
Swift 4 Program for
Find all distinct subsets of given sum
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ top: StackNode? )
{
self.element = element;
self.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top  != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top  != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
func peek()->Int
{
return self.top!.element;
}
}
class SubSetSum
{
var stack: MyStack;
init()
{
self.stack = MyStack();
}
func show(_ top: StackNode? )
{
if (top == nil)
{
return;
}
// Get top element
let element: Int = top!.element;
// next top
self.show(top!.next);
// Display element
print(" ", element, terminator: "");
}
// Finding the all distinct subsets of given sum
func subset(_ location: Int, _ sum: Int)
{
if (sum == 0)
{
// Display subset
print(" [", terminator: "");
self.show(self.stack.top);
print(" ]");
}
var i: Int = location;
while (i <= sum)
{
self.stack.push(i);
self.subset(i, sum - i);
// Remove top element of stack
self.stack.pop();
i += 1;
}
}
// Handles the request to find subset Sum
func findSubset(_ sum: Int)
{
if (sum <= 0)
{
return;
}
print("\n Subset of sum ", sum ," ");
self.subset(1, sum);
}
}
func main()
{
// Test case
}
main();``````

#### Output

`````` Subset of sum  5
[  1  1  1  1  1 ]
[  1  1  1  2 ]
[  1  1  3 ]
[  1  2  2 ]
[  1  4 ]
[  2  3 ]
[  5 ]

Subset of sum  10
[  1  1  1  1  1  1  1  1  1  1 ]
[  1  1  1  1  1  1  1  1  2 ]
[  1  1  1  1  1  1  1  3 ]
[  1  1  1  1  1  1  2  2 ]
[  1  1  1  1  1  1  4 ]
[  1  1  1  1  1  2  3 ]
[  1  1  1  1  1  5 ]
[  1  1  1  1  2  2  2 ]
[  1  1  1  1  2  4 ]
[  1  1  1  1  3  3 ]
[  1  1  1  1  6 ]
[  1  1  1  2  2  3 ]
[  1  1  1  2  5 ]
[  1  1  1  3  4 ]
[  1  1  1  7 ]
[  1  1  2  2  2  2 ]
[  1  1  2  2  4 ]
[  1  1  2  3  3 ]
[  1  1  2  6 ]
[  1  1  3  5 ]
[  1  1  4  4 ]
[  1  1  8 ]
[  1  2  2  2  3 ]
[  1  2  2  5 ]
[  1  2  3  4 ]
[  1  2  7 ]
[  1  3  3  3 ]
[  1  3  6 ]
[  1  4  5 ]
[  1  9 ]
[  2  2  2  2  2 ]
[  2  2  2  4 ]
[  2  2  3  3 ]
[  2  2  6 ]
[  2  3  5 ]
[  2  4  4 ]
[  2  8 ]
[  3  3  4 ]
[  3  7 ]
[  4  6 ]
[  5  5 ]
[  10 ]``````
``````/*
Kotlin Program for
Find all distinct subsets of given sum
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, top: StackNode? )
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size > 0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
fun peek(): Int
{
return this.top!!.element;
}
}
class SubSetSum
{
var stack: MyStack;
constructor()
{
this.stack = MyStack();
}
fun show(top: StackNode ? ): Unit
{
if (top == null)
{
return;
}
// Get top element
var element: Int = top.element;
// next top
this.show(top.next);
// Display element
print(" " + element);
}
// Finding the all distinct subsets of given sum
fun subset(location: Int, sum: Int): Unit
{
if (sum == 0)
{
// Display subset
print(" [");
this.show(this.stack.top);
print(" ]\n");
}
var i: Int = location;
while (i <= sum)
{
this.stack.push(i);
this.subset(i, sum - i);
// Remove top element of stack
this.stack.pop();
i += 1;
}
}
// Handles the request to find subset Sum
fun findSubset(sum: Int): Unit
{
if (sum <= 0)
{
return;
}
print("\n Subset of sum " + sum + " \n");
this.subset(1, sum);
}
}
fun main(args: Array < String > ): Unit
{
// Test case
}``````

#### Output

`````` Subset of sum 5
[ 1 1 1 1 1 ]
[ 1 1 1 2 ]
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 4 ]
[ 2 3 ]
[ 5 ]

Subset of sum 10
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 1 2 ]
[ 1 1 1 1 1 1 1 3 ]
[ 1 1 1 1 1 1 2 2 ]
[ 1 1 1 1 1 1 4 ]
[ 1 1 1 1 1 2 3 ]
[ 1 1 1 1 1 5 ]
[ 1 1 1 1 2 2 2 ]
[ 1 1 1 1 2 4 ]
[ 1 1 1 1 3 3 ]
[ 1 1 1 1 6 ]
[ 1 1 1 2 2 3 ]
[ 1 1 1 2 5 ]
[ 1 1 1 3 4 ]
[ 1 1 1 7 ]
[ 1 1 2 2 2 2 ]
[ 1 1 2 2 4 ]
[ 1 1 2 3 3 ]
[ 1 1 2 6 ]
[ 1 1 3 5 ]
[ 1 1 4 4 ]
[ 1 1 8 ]
[ 1 2 2 2 3 ]
[ 1 2 2 5 ]
[ 1 2 3 4 ]
[ 1 2 7 ]
[ 1 3 3 3 ]
[ 1 3 6 ]
[ 1 4 5 ]
[ 1 9 ]
[ 2 2 2 2 2 ]
[ 2 2 2 4 ]
[ 2 2 3 3 ]
[ 2 2 6 ]
[ 2 3 5 ]
[ 2 4 4 ]
[ 2 8 ]
[ 3 3 4 ]
[ 3 7 ]
[ 4 6 ]
[ 5 5 ]
[ 10 ]``````

## Time Complexity

The time complexity of the code depends on the number of subsets that sum up to the given sum. For a given sum `s`, the number of subsets can be represented by the partition function, which grows exponentially with `s`. Therefore, the time complexity of the code is exponential, O(2^n), where `n` is the given sum.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post