Find all distinct subsets of given sum
Here given code implementation process.
// 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 ]
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