Split a number into smaller numbers

In this article, we will explore a problem where we need to split a given number into smaller numbers. We'll provide an explanation of the problem, a suitable example, the algorithm and pseudocode to solve it, and an explanation of the resulting output. Let's dive in!

Problem Statement

The problem is to divide a positive number into a combination of smaller numbers that sum up to the original number. For example, if the input is 5, we need to find all possible combinations of smaller numbers that add up to 5.

Example

Let's consider the number 5. We want to find all possible combinations of smaller numbers that add up to 5. The expected output should be:

Split number 5
[1 1 1 1 1]
[1 1 1 2]
[1 1 3]
[1 2 2]
[1 4]
[2 3]

Similarly, if we consider the number 6, the expected output should be:

Split number 6
[1 1 1 1 1 1]
[1 1 1 1 2]
[1 1 1 3]
[1 1 2 2]
[1 1 4]
[1 2 3]
[1 5]
[2 2 2]
[2 4]
[3 3]

Algorithm

To solve this problem, we can use a recursive approach. Here is the algorithm:

1. Create a stack data structure to store the numbers.
2. Create a function to split the number.
3. If the number is 0 and the stack size is greater than 1, display the numbers in the stack as a valid split.
4. Iterate from the current location to the given number.
5. Push the current number onto the stack.
6. Recursively call the split function with the updated number and location.
7. Pop the top element from the stack.
8. Repeat steps 4-7 until all possible combinations are found.

The time complexity of this algorithm depends on the number of valid splits. In the worst case, when the number is n, the time complexity is O(2^n) because there can be 2^n possible splits.

Pseudocode

Here is the pseudocode for the splitNumber function:

function splitNumber(num):
    if num <= 0:
        return

    stack = newStack()
    print "Split number " + num
    
    split(stack, 1, num)

function split(stack, location, num):
    if num == 0 and size(stack) > 1:
        print "[" + show(stack.top) + "]"
    
    for i from location to num:
        push(stack, i)
        split(stack, i, num - i)
        pop(stack)

Code Solution

Here given code implementation process.

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// C program 
// Split a number into smaller numbers
#include <stdio.h>

#include <stdlib.h>
 // Define stack node
struct StackNode
{
	int element;
	struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
	struct StackNode *top;
	int size;
};
struct MyStack *newStack()
{
	//Make a stack
	struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
	if (stack != NULL)
	{
		//Set node values
		stack->top = NULL;
		stack->size = 0;
	}
	else
	{
		printf("\n Memory overflow when create new stack\n");
	}
}
//Create a new node of stack
struct StackNode *newNode(int element, struct StackNode *next)
{
	//Make a new node
	struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
	if (node == NULL)
	{
		printf("\n Memory overflow when create new stack Node \n");
	}
	else
	{
		node->element = element;
		node->next = next;
	}
	return node;
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
	if (stack->size > 0 && stack->top != NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
	// Add stack element
	stack->top = newNode(element, stack->top);
	stack->size++;
}
// return top element of stack
int peek(struct MyStack *stack)
{
	return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
	if (isEmpty(stack) == 0)
	{
		struct StackNode *temp = stack->top;
		// Change top element of stack
		stack->top = temp->next;
		// remove previous top
		free(temp);
		temp = NULL;
		stack->size--;
	}
}
int size(struct MyStack *stack)
{
	return stack->size;
}
// Display stack elements in reverse order
void show(struct StackNode *top)
{
	if (top == NULL)
	{
		return;
	}
	// Get top element
	int element = top->element;
	// next top
	show(top->next);
	// Display element
	printf("  %d", element);
}
// Divide a positive number into a smaller number that is equal to the original number
void split(struct MyStack *stack, int location, int num)
{
	if (num == 0 && size(stack) > 1)
	{
		// Display split
		printf(" [");
		show(stack->top);
		printf("  ]\n");
	}
	for (int i = location; i <= num; i++)
	{
		// Add stack element
		push(stack, i);
		split(stack, i, num - i);
		// Remove top element of stack
		pop(stack);
	}
}
// Handles the request to find subset of given number
void splitNumber(int num)
{
	if (num <= 0)
	{
		return;
	}
	// Define a stack
	struct MyStack *stack = newStack();
	printf("\n Split number %d \n", num);
	split(stack, 1, num);
}
int main()
{
	// Test case
	splitNumber(5);
	splitNumber(6);
	return 0;
}

 Split number 5
 [  1  1  1  1  1  ]
 [  1  1  1  2  ]
 [  1  1  3  ]
 [  1  2  2  ]
 [  1  4  ]
 [  2  3  ]

 Split number 6
 [  1  1  1  1  1  1  ]
 [  1  1  1  1  2  ]
 [  1  1  1  3  ]
 [  1  1  2  2  ]
 [  1  1  4  ]
 [  1  2  3  ]
 [  1  5  ]
 [  2  2  2  ]
 [  2  4  ]
 [  3  3  ]

/*
    Java Program for
    Split a number into smaller numbers
*/
// 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 int size()
	{
		return this.size;
	}
}
public class Partition
{
	public MyStack stack;
	public Partition()
	{
		this.stack = new MyStack();
	}
	// Display stack elements in reverse order
	public void show(StackNode node)
	{
		if (node == null)
		{
			return;
		}
		// Get top element
		int element = node.element;
		// next top
		show(node.next);
		// Display element
		System.out.print("  " + element);
	}
	public void split(int location, int num)
	{
		if (num == 0 && this.stack.size() > 1)
		{
			// Display split
			System.out.print(" [");
			show(this.stack.top);
			System.out.print(" ]\n");
		}
		for (int i = location; i <= num; i++)
		{
			// Add stack element
			this.stack.push(i);
			split(i, num - i);
			// Remove top element of stack
			this.stack.pop();
		}
	}
	// Handles the request to find split Sum
	public void splitNumber(int num)
	{
		if (num <= 0)
		{
			return;
		}
		System.out.print("\n Split number " + num + " \n");
		split(1, num);
	}
	public static void main(String[] args)
	{
		Partition task = new Partition();
		// Test case
		task.splitNumber(5);
		task.splitNumber(6);
	}
}

 Split number 5
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program for
    Split a number into smaller numbers
*/
// 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;
			// remove previous top
			temp = NULL;
			this->size--;
		}
	}
	// return top element of stack
	int peek()
	{
		return this->top->element;
	}
	int getSize()
	{
		return this->size;
	}
};
class Partition
{
	public: MyStack *stack;
	Partition()
	{
		this->stack = new MyStack();
	}
	// Display stack elements in reverse order
	void show(StackNode *node)
	{
		if (node == NULL)
		{
			return;
		}
		// Get top element
		int element = node->element;
		// next top
		this->show(node->next);
		// Display element
		cout << "  " << element;
	}
	void split(int location, int num)
	{
		if (num == 0 && this->stack->getSize() > 1)
		{
			// Display split
			cout << " [";
			this->show(this->stack->top);
			cout << " ]\n";
		}
		for (int i = location; i <= num; i++)
		{
			// Add stack element
			this->stack->push(i);
			this->split(i, num - i);
			// Remove top element of stack
			this->stack->pop();
		}
	}
	// Handles the request to find split Sum
	void splitNumber(int num)
	{
		if (num <= 0)
		{
			return;
		}
		cout << "\n Split number " << num << " \n";
		this->split(1, num);
	}
};
int main()
{
	Partition task = Partition();
	// Test case
	task.splitNumber(5);
	task.splitNumber(6);
	return 0;
}

 Split number 5
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

// Include namespace system
using System;
/*
    C# Program for
    Split a number into smaller numbers
*/
// 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 int getSize()
	{
		return this.size;
	}
}
public class Partition
{
	public MyStack stack;
	public Partition()
	{
		this.stack = new MyStack();
	}
	// Display stack elements in reverse order
	public void show(StackNode node)
	{
		if (node == null)
		{
			return;
		}
		// Get top element
		int element = node.element;
		// next top
		show(node.next);
		// Display element
		Console.Write("  " + element);
	}
	public void split(int location, int num)
	{
		if (num == 0 && this.stack.getSize() > 1)
		{
			// Display split
			Console.Write(" [");
			show(this.stack.top);
			Console.Write(" ]\n");
		}
		for (int i = location; i <= num; i++)
		{
			// Add stack element
			this.stack.push(i);
			split(i, num - i);
			// Remove top element of stack
			this.stack.pop();
		}
	}
	// Handles the request to find split Sum
	public void splitNumber(int num)
	{
		if (num <= 0)
		{
			return;
		}
		Console.Write("\n Split number " + num + " \n");
		split(1, num);
	}
	public static void Main(String[] args)
	{
		Partition task = new Partition();
		// Test case
		task.splitNumber(5);
		task.splitNumber(6);
	}
}

 Split number 5
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

<?php
/*
    Php Program for
    Split a number into smaller numbers
*/
// 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;
	}
	public	function getSize()
	{
		return $this->size;
	}
}
class Partition
{
	public $stack;

	function __construct()
	{
		$this->stack = new MyStack();
	}
	// Display stack elements in reverse order
	public	function show($node)
	{
		if ($node == null)
		{
			return;
		}
		// Get top element
		$element = $node->element;
		// next top
		$this->show($node->next);
		// Display element
		echo "  ". $element;
	}
	public	function split($location, $num)
	{
		if ($num == 0 && $this->stack->getSize() > 1)
		{
			// Display split
			echo " [";
			$this->show($this->stack->top);
			echo " ]\n";
		}
		for ($i = $location; $i <= $num; $i++)
		{
			// Add stack element
			$this->stack->push($i);
			$this->split($i, $num - $i);
			// Remove top element of stack
			$this->stack->pop();
		}
	}
	// Handles the request to find split Sum
	public	function splitNumber($num)
	{
		if ($num <= 0)
		{
			return;
		}
		echo "\n Split number ". $num ." \n";
		$this->split(1, $num);
	}
}

function main()
{
	$task = new Partition();
	// Test case
	$task->splitNumber(5);
	$task->splitNumber(6);
}
main();

 Split number 5
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

/*
    Node Js Program for
    Split a number into smaller numbers
*/
// 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;
	}
	getSize()
	{
		return this.size;
	}
}
class Partition
{
	constructor()
	{
		this.stack = new MyStack();
	}
	// Display stack elements in reverse order
	show(node)
	{
		if (node == null)
		{
			return;
		}
		// Get top element
		var element = node.element;
		// next top
		this.show(node.next);
		// Display element
		process.stdout.write("  " + element);
	}
	split(location, num)
	{
		if (num == 0 && this.stack.getSize() > 1)
		{
			// Display split
			process.stdout.write(" [");
			this.show(this.stack.top);
			process.stdout.write(" ]\n");
		}
		for (var i = location; i <= num; i++)
		{
			// Add stack element
			this.stack.push(i);
			this.split(i, num - i);
			// Remove top element of stack
			this.stack.pop();
		}
	}
	// Handles the request to find split Sum
	splitNumber(num)
	{
		if (num <= 0)
		{
			return;
		}
		process.stdout.write("\n Split number " + num + " \n");
		this.split(1, num);
	}
}

function main()
{
	var task = new Partition();
	// Test case
	task.splitNumber(5);
	task.splitNumber(6);
}
main();

 Split number 5
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

#  Python 3 Program for
#  Split a number into smaller numbers

#  Define stack node
class StackNode :
	
	def __init__(self, element, next) :
		self.element = element
		self.next = next
	

#  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
	
	def getSize(self) :
		return self.size
	

class Partition :
	
	def __init__(self) :
		self.stack = MyStack()
	
	#  Display stack elements in reverse order
	def show(self, node) :
		if (node == None) :
			return
		
		#  Get top element
		element = node.element
		#  next top
		self.show(node.next)
		#  Display element
		print(element, end = " ")
	
	def split(self, location, num) :
		if (num == 0 and self.stack.getSize() > 1) :
			#  Display split
			print(end = " [ ")
			self.show(self.stack.top)
			print("]")
		
		i = location
		while (i <= num) :
			#  Add stack element
			self.stack.push(i)
			self.split(i, num - i)
			#  Remove top element of stack
			self.stack.pop()
			i += 1
		
	
	#  Handles the request to find split Sum
	def splitNumber(self, num) :
		if (num <= 0) :
			return
		
		print("\n Split number ", num ," ")
		self.split(1, num)
	

def main() :
	task = Partition()
	#  Test case
	task.splitNumber(5)
	task.splitNumber(6)

if __name__ == "__main__": main()

 Split number  5
 [ 1 1 1 1 1 ]
 [ 1 1 1 2 ]
 [ 1 1 3 ]
 [ 1 2 2 ]
 [ 1 4 ]
 [ 2 3 ]

 Split number  6
 [ 1 1 1 1 1 1 ]
 [ 1 1 1 1 2 ]
 [ 1 1 1 3 ]
 [ 1 1 2 2 ]
 [ 1 1 4 ]
 [ 1 2 3 ]
 [ 1 5 ]
 [ 2 2 2 ]
 [ 2 4 ]
 [ 3 3 ]

#  Ruby Program for
#  Split a number into smaller numbers

#  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

	def getSize() 
		return self.size
	end

end

class Partition  
	# Define the accessor and reader of class Partition  
	attr_reader :stack
	attr_accessor :stack
 
	
	def initialize() 
		self.stack = MyStack.new()
	end

	#  Display stack elements in reverse order
	def show(node) 
		if (node == nil) 
			return
		end

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

	def split(location, num) 
		if (num == 0 && self.stack.getSize() > 1) 
			#  Display split
			print(" [")
			self.show(self.stack.top)
			print(" ]\n")
		end

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

	end

	#  Handles the request to find split Sum
	def splitNumber(num) 
		if (num <= 0) 
			return
		end

		print("\n Split number ", num ," \n")
		self.split(1, num)
	end

end

def main() 
	task = Partition.new()
	#  Test case
	task.splitNumber(5)
	task.splitNumber(6)
end

main()

 Split number 5 
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6 
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

/*
    Scala Program for
    Split a number into smaller numbers
*/
// 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;
	}
	def getSize(): Int = {
		return this.size;
	}
}
class Partition(var stack: MyStack)
{
	def this()
	{
		this(new MyStack());
	}
	// Display stack elements in reverse order
	def show(node: StackNode): Unit = {
		if (node == null)
		{
			return;
		}
		// Get top element
		var element: Int = node.element;
		// next top
		this.show(node.next);
		// Display element
		print("  " + element);
	}
	def split(location: Int, num: Int): Unit = {
		if (num == 0 && this.stack.getSize() > 1)
		{
			// Display split
			print(" [");
			this.show(this.stack.top);
			print(" ]\n");
		}
		var i: Int = location;
		while (i <= num)
		{
			// Add stack element
			this.stack.push(i);
			this.split(i, num - i);
			// Remove top element of stack
			this.stack.pop();
			i += 1;
		}
	}
	// Handles the request to find split Sum
	def splitNumber(num: Int): Unit = {
		if (num <= 0)
		{
			return;
		}
		print("\n Split number " + num + " \n");
		this.split(1, num);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Partition = new Partition();
		// Test case
		task.splitNumber(5);
		task.splitNumber(6);
	}
}

 Split number 5
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

/*
    Swift 4 Program for
    Split a number into smaller numbers
*/
// Define stack node
class StackNode
{
	var element: Int;
	var next: StackNode? ;
	init(_ element: Int, _ next: StackNode? )
	{
		self.element = element;
		self.next = next;
	}
}
// 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;
	}
	func getSize()->Int
	{
		return self.size;
	}
}
class Partition
{
	var stack: MyStack ;
	init()
	{
		self.stack = MyStack();
	}
	// Display stack elements in reverse order
	func show(_ node: StackNode? )
	{
		if (node == nil)
		{
			return;
		}
		// Get top element
		let element: Int = node!.element;
		// next top
		self.show(node!.next);
		// Display element
		print("", element, terminator: " ");
	}
	func split(_ location: Int, _ num: Int)
	{
		if (num == 0 && self.stack.getSize() > 1)
		{
			// Display split
			print(" [ ", terminator: "");
			self.show(self.stack.top);
			print(" ]");
		}
		var i: Int = location;
		while (i <= num)
		{
			// Add stack element
			self.stack.push(i);
			self.split(i, num - i);
			// Remove top element of stack
			self.stack.pop();
			i += 1;
		}
	}
	// Handles the request to find split Sum
	func splitNumber(_ num: Int)
	{
		if (num <= 0)
		{
			return;
		}
		print("\n Split number ", num ," ");
		self.split(1, num);
	}
}
func main()
{
	let task: Partition = Partition();
	// Test case
	task.splitNumber(5);
	task.splitNumber(6);
}
main();

 Split number  5
 [  1  1  1  1  1  ]
 [  1  1  1  2  ]
 [  1  1  3  ]
 [  1  2  2  ]
 [  1  4  ]
 [  2  3  ]

 Split number  6
 [  1  1  1  1  1  1  ]
 [  1  1  1  1  2  ]
 [  1  1  1  3  ]
 [  1  1  2  2  ]
 [  1  1  4  ]
 [  1  2  3  ]
 [  1  5  ]
 [  2  2  2  ]
 [  2  4  ]
 [  3  3  ]

/*
    Kotlin Program for
    Split a number into smaller numbers
*/
// Define stack node
class StackNode
{
	var element: Int;
	var next: StackNode ? ;
	constructor(element: Int, next: StackNode ? )
	{
		this.element = element;
		this.next = next;
	}
}
// 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;
	}
	fun size(): Int
	{
		return this.size;
	}
}
class Partition
{
	var stack: MyStack;
	constructor()
	{
		this.stack = MyStack();
	}
	// Display stack elements in reverse order
	fun show(node: StackNode ? ): Unit
	{
		if (node == null)
		{
			return;
		}
		// Get top element
		var element: Int = node.element;
		// next top
		this.show(node.next);
		// Display element
		print("  " + element);
	}
	fun split(location: Int, num: Int): Unit
	{
		if (num == 0 && this.stack.size() > 1)
		{
			// Display split
			print(" [");
			this.show(this.stack.top);
			print(" ]\n");
		}
		var i: Int = location;
		while (i <= num)
		{
			// Add stack element
			this.stack.push(i);
			this.split(i, num - i);
			// Remove top element of stack
			this.stack.pop();
			i += 1;
		}
	}
	// Handles the request to find split Sum
	fun splitNumber(num: Int): Unit
	{
		if (num <= 0)
		{
			return;
		}
		print("\n Split number " + num + " \n");
		this.split(1, num);
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Partition = Partition();
	// Test case
	task.splitNumber(5);
	task.splitNumber(6);
}

 Split number 5
 [  1  1  1  1  1 ]
 [  1  1  1  2 ]
 [  1  1  3 ]
 [  1  2  2 ]
 [  1  4 ]
 [  2  3 ]

 Split number 6
 [  1  1  1  1  1  1 ]
 [  1  1  1  1  2 ]
 [  1  1  1  3 ]
 [  1  1  2  2 ]
 [  1  1  4 ]
 [  1  2  3 ]
 [  1  5 ]
 [  2  2  2 ]
 [  2  4 ]
 [  3  3 ]

Resultant Output Explanation

The resultant output shows all the valid splits for the given numbers. Each line represents a valid split, where the numbers in brackets represent the combination of smaller numbers that add up to the original number.

For example, in the output for number 5, the line [1 1 1 1 1] means that the number 5 can be split into five 1s. Similarly, [1 4] represents a split where the number 5 is divided into 1 and 4.

The output for number 6 follows the same pattern, showing all possible combinations of smaller numbers that add up to 6.

Finally

In this article, we explored the problem of splitting a number into smaller numbers. We provided a detailed explanation of the problem, a suitable example, the algorithm, and pseudocode to solve it. We also explained the resultant output and discussed the time complexity of the code.

By using the recursive approach and the stack data structure, we can find all possible combinations of smaller numbers that sum up to the given number. This problem can be useful in various scenarios, such as partitioning resources or solving optimization problems.