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
Call task.findSubset(5)
Call task.findSubset(10)
Algorithm
- Define a custom class
StackNode
to represent a node in the stack. It will have two fields:element
to store the value andnext
to point to the next node in the stack. - Define another custom class
MyStack
to represent the stack. It will have two fields:top
to point to the top node in the stack andsize
to store the number of elements in the stack. It will also have functionspush
,pop
,peek
, andisEmpty
. - Define a class
SubSetSum
with a fieldstack
of typeMyStack
. In the constructor, initializestack
to a new instance ofMyStack
. - Define a function
show
that takes a nodetop
as a parameter and recursively prints the elements of the stack starting fromtop
. - Define a function
subset
that takes two parameters:location
andsum
. This function will find all subsets of the givensum
starting from thelocation
element. - If
sum
is 0, print the current subset by calling theshow
function onstack.top
. - For each number
i
fromlocation
tosum
, do the following:- Push
i
onto the stack. - Call the
subset
function withi
as the newlocation
andsum - i
as the newsum
. - Pop the top element from the stack to backtrack and try the next number.
- Push
- Define a function
findSubset
that takes a parametersum
and finds all subsets of the givensum
. - If
sum
is less than or equal to 0, return. - Print "Subset of sum" and the value of
sum
. - Call the
subset
function withlocation = 1
and the givensum
. - In the
main
function, create an instance ofSubSetSum
calledtask
. - Call
task.findSubset(5)
andtask.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++)
{
// Add stack element
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--;
}
}
// return top element of stack
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++)
{
// Add stack element
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)
{
SubSetSum task = new SubSetSum();
// Test case
task.findSubset(5);
task.findSubset(10);
}
}
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--;
}
}
// return top element of stack
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++)
{
// Add stack element
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()
{
SubSetSum task = SubSetSum();
// Test case
task.findSubset(5);
task.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 ]
// 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--;
}
}
// return top element of stack
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++)
{
// Add stack element
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)
{
SubSetSum task = new SubSetSum();
// Test case
task.findSubset(5);
task.findSubset(10);
}
}
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--;
}
}
// return top element of stack
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++)
{
// Add stack element
$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()
{
$task = new SubSetSum();
// Test case
$task->findSubset(5);
$task->findSubset(10);
}
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--;
}
}
// return top element of stack
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++)
{
// Add stack element
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()
{
var task = new SubSetSum();
// Test case
task.findSubset(5);
task.findSubset(10);
}
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
# return top element of stack
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) :
# Add stack element
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() :
task = SubSetSum()
# Test case
task.findSubset(5)
task.findSubset(10)
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_reader :element, :next
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_reader :top, :size
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
# return top element of stack
def peek()
return self.top.element
end
end
class SubSetSum
# Define the accessor and reader of class SubSetSum
attr_reader :stack
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)
# Add stack element
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()
task = SubSetSum.new()
# Test case
task.findSubset(5)
task.findSubset(10)
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;
}
}
// return top element of stack
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)
{
// Add stack element
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
task.findSubset(5);
task.findSubset(10);
}
}
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;
}
}
// return top element of stack
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)
{
// Add stack element
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()
{
let task: SubSetSum = SubSetSum();
// Test case
task.findSubset(5);
task.findSubset(10);
}
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;
}
}
// return top element of stack
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)
{
// Add stack element
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
{
var task: SubSetSum = SubSetSum();
// Test case
task.findSubset(5);
task.findSubset(10);
}
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.
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.
New Comment