Skip to main content

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

  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++)
	{
		// 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.

Last updated on by Kalkicode




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.

New Comment