Java Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself

This is a java program to find the number of ways to write a given number as sum of numbers less than the number itself. We start with the number, number minus one is the next partition and so on, till all one’s are the last partition where we stop.

Here is the source code of the Java Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to find the number of ways to write a number as a sum of smaller than the number itself
import java.util.Scanner;
 
public class NumberOf_Unique_Partitions 
{
    public static void print(int[] p, int n, int count) 
    {
        for (int i = 0; i < n; i++)
            System.out.print(p[i] + " ");
        System.out.println();
        int j;
        for (j = 0; j < n; j++) 
        {
            if (p[j] == 1)
                continue;
            else
                break;
        }
        if (j == n)
            System.out
                    .println("The number of ways to write a number as a sum of number smaller than itself is :"
                            + (count - 1));
    }
 
    public static void generateUniquePartition(int n) 
    {
        int[] p = new int[n];
        int k = 0, count = 0;
        p[k] = n;
        while (true) 
        {
            count++;
            print(p, k + 1, count);
            int rem_value = 0;
            while (k >= 0 && p[k] == 1) 
            {
                rem_value += p[k];
                k--;
            }
            if (k < 0)
                return;
 
            p[k]--;
            rem_value++;
 
            while (rem_value > p[k]) 
            {
                p[k + 1] = p[k];
                rem_value -= p[k];
                k++;
            }
            p[k + 1] = rem_value;
            k++;
        }
    }
 
    public static void main(String args[]) 
    {
        System.out.println("Unique Partitioning of a given number");
        System.out.println("Enter the number:");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        generateUniquePartition(n);
        sc.close();
    }
}

Output:

$ javac NumberOf_Unique_Partitions.java
$ java NumberOf_Unique_Partitions
 
Unique Partitioning of a given number
Enter the number:
6
6 
5 1 
4 2 
4 1 1 
3 3 
3 2 1 
3 1 1 1 
2 2 2 
2 2 1 1 
2 1 1 1 1 
1 1 1 1 1 1 
The number of ways to write as a sum of number smaller than itself is :10

Related posts:

Java Program to Implement Wagner and Fisher Algorithm for online String Matching
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
Retrieve User Information in Spring Security
Spring Webflux and CORS
Spring Boot - Tomcat Port Number
Create Java Applet to Simulate Any Sorting Technique
Guide to Selenium with JUnit / TestNG
Guide to UUID in Java
Java Program to find the number of occurrences of a given number using Binary Search approach
Guide to the Java Queue Interface
Registration – Password Strength and Rules
Hamcrest Collections Cookbook
Java Program to Implement AVL Tree
Enum trong java
Send email with SMTPS (eg. Google GMail)
Arrays.asList vs new ArrayList(Arrays.asList())
Converting a List to String in Java
Testing in Spring Boot
Spring Data JPA Delete and Relationships
Java Program to Implement the Alexander Bogomolny’s UnOrdered Permutation Algorithm for Elements Fro...
Java Program to Perform LU Decomposition of any Matrix
Runnable vs. Callable in Java
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
Queue và PriorityQueue trong Java
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Tạo chương trình Java đầu tiên sử dụng Eclipse
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Giới thiệu Google Guice – Injection, Scope
Java Program to Implement TreeSet API
Java Program to Represent Graph Using Incidence Matrix
Xử lý ngoại lệ trong Java (Exception Handling)
Java Program to Implement Doubly Linked List