Data Modelling & AI Data Structure & Algorithm

Print all possible ways to split an array into K subsets

23 June 2025

0

Given an array arr[] of size N and an integer K, the task is to print all possible ways to split the given array into K subsets.

Examples:

Input: arr[] = { 1, 2, 3 }, K = 2
Output: { {{ 1, 2 }, { 3 }}, {{ 1, 3 }, { 2 }}, {{ 1 }, { 2, 3 }}}.

Input: arr[] = { 1, 2, 3, 4 }, K = 2
Output: { {{ 1, 2, 3 }, { 4 }}, {{ 1, 2, 4 }, { 3 }}, {{ 1, 2 }, { 3, 4 }}, {{ 1, 3, 4 }, { 2 }}, {{ 1, 3 }, { 2, 4 }}, {{ 1, 4 }, { 2, 3 }}, {{ 1 }, { 2 3, 4 }} }

Approach: The problem can be solved using backtracking to generate and print all the subsets. Follow the steps below to solve the problem:

Traverse the array and insert elements into any one of the K subsets using the following recurrence relation:

PartitionSub(i, K, N)

{

for (j = 0; j < K; j++) {

sub[j].push_back(arr[i])

PartitionSub(i + 1, K, N)

sub[j].pop_back()

}

}

If K is equal to 0 or K > N, then subsets cannot be generated.
If count of array elements inserted into K subsets equal to N, then print the elements of the subset.

C++

// C++ program for the above approach 
 
#include <bits/stdc++.h> 
using namespace std; 
 
// arr: Store input array 
// i: Stores current index of arr 
// N: Stores length of arr 
// K: Stores count of subsets 
// nos: Stores count of feasible subsets formed 
// v: Store K subsets of the given array 
 
// Utility function to find all possible 
// ways to split array into K subsets 
void PartitionSub(int arr[], int i, 
                int N, int K, int nos, 
                vector<vector<int> >& v) 
{ 
 
    // If count of elements in K subsets 
    // are greater than or equal to N 
    if (i >= N) { 
 
        // If count of subsets 
        // formed is equal to K 
        if (nos == K) { 
 
            // Print K subsets by splitting 
            // array into K subsets 
            for (int x = 0; x < v.size(); x++) { 
 
                cout << "{ "; 
 
                // Print current subset 
                for (int y = 0; y < v[x].size(); y++) { 
                    cout << v[x][y]; 
 
                    // If current element is the last 
                    // element of the subset 
                    if (y == v[x].size() - 1) { 
 
                        cout << " "; 
                    } 
 
                    // Otherwise 
                    else { 
 
                        cout << ", "; 
                    } 
                } 
 
                if (x == v.size() - 1) { 
 
                    cout << "}"; 
                } 
                else { 
 
                    cout << "}, "; 
                } 
            } 
            cout << endl; 
        } 
 
        return; 
    } 
 
    for (int j = 0; j < K; j++) { 
 
        // If any subset is occupied, 
        // then push the element 
        // in that first 
        if (v[j].size() > 0) { 
            v[j].push_back(arr[i]); 
 
            // Recursively do the same 
            // for remaining elements 
            PartitionSub(arr, i + 1, N, K, nos, v); 
 
            // Backtrack 
            v[j].pop_back(); 
        } 
 
        // Otherwise, push it in an empty 
        // subset and increase the 
        // subset count by 1 
        else { 
 
            v[j].push_back(arr[i]); 
            PartitionSub(arr, i + 1, N, K, nos + 1, v); 
            v[j].pop_back(); 
 
            // Break to avoid the case of going in 
            // other empty subsets, if available, 
            // and forming the same combination 
            break; 
        } 
    } 
} 
 
// Function to find all possible ways to 
// split array into K subsets 
void partKSubsets(int arr[], int N, int K) 
{ 
 
    // Stores K subset by splitting array 
    // into K subsets 
    vector<vector<int> > v(K); 
 
    // Size of each subset must 
    // be less than the number of elements 
    if (K == 0 || K > N) { 
 
        cout << "Not Possible" << endl; 
    } 
    else { 
 
        cout << "The Subset Combinations are: " << endl; 
        PartitionSub(arr, 0, N, K, 0, v); 
    } 
} 
 
// Driver Code 
int main() 
{ 
 
    // Given array 
    int arr[] = { 1, 2, 3, 4 }; 
 
    // Given K 
    int K = 2; 
 
    // Size of the array 
    int N = sizeof(arr) / sizeof(arr[0]); 
 
    // Prints all possible 
    // splits into subsets 
    partKSubsets(arr, N, K); 
} 

Java

// Java program for above approach
import java.util.*;
import java.lang.*;
class Gfg
{
 
  // arr: Store input array 
  // i: Stores current index of arr 
  // N: Stores length of arr 
  // K: Stores count of subsets 
  // nos: Stores count of feasible subsets formed 
  // v: Store K subsets of the given array 
 
  // Utility function to find all possible 
  // ways to split array into K subsets 
  static void PartitionSub(int arr[], int i, 
                           int N, int K, int nos, 
                           ArrayList<ArrayList<Integer>> v) 
  { 
 
    // If count of elements in K subsets 
    // are greater than or equal to N 
    if (i >= N)
    { 
 
      // If count of subsets 
      // formed is equal to K 
      if (nos == K) 
      { 
 
        // Print K subsets by splitting 
        // array into K subsets 
        for (int x = 0; x < v.size(); x++)
        { 
 
          System.out.print("{ "); 
 
          // Print current subset 
          for (int y = 0; y < v.get(x).size(); y++)
          { 
            System.out.print(v.get(x).get(y)); 
 
            // If current element is the last 
            // element of the subset 
            if (y == v.get(x).size() - 1)
            { 
              System.out.print(" "); 
            } 
 
            // Otherwise 
            else
            { 
              System.out.print(", "); 
            } 
          } 
 
          if (x == v.size() - 1)
          { 
            System.out.print("}"); 
          } 
          else
          { 
            System.out.print("}, "); 
          } 
        } 
        System.out.println();; 
      } 
      return; 
    } 
 
    for (int j = 0; j < K; j++)
    { 
 
      // If any subset is occupied, 
      // then push the element 
      // in that first 
      if (v.get(j).size() > 0)
      { 
        v.get(j).add(arr[i]); 
 
        // Recursively do the same 
        // for remaining elements 
        PartitionSub(arr, i + 1, N, K, nos, v); 
 
        // Backtrack 
        v.get(j).remove(v.get(j).size()-1); 
      } 
 
      // Otherwise, push it in an empty 
      // subset and increase the 
      // subset count by 1 
      else
      { 
 
        v.get(j).add(arr[i]); 
        PartitionSub(arr, i + 1, N, K, nos + 1, v); 
        v.get(j).remove(v.get(j).size()-1); 
 
        // Break to avoid the case of going in 
        // other empty subsets, if available, 
        // and forming the same combination 
        break; 
      } 
    } 
  } 
 
  // Function to find all possible ways to 
  // split array into K subsets 
  static void partKSubsets(int arr[], int N, int K) 
  { 
 
    // Stores K subset by splitting array 
    // into K subsets 
    ArrayList<ArrayList<Integer>> v = new ArrayList<>();
 
    for(int i = 0; i < K; i++)
      v.add(new ArrayList<>());
 
    // Size of each subset must 
    // be less than the number of elements 
    if (K == 0 || K > N)
    { 
      System.out.println("Not Possible"); 
    } 
    else
    { 
      System.out.println("The Subset Combinations are: "); 
      PartitionSub(arr, 0, N, K, 0, v); 
    } 
  } 
 
  // Driver function
  public static void main (String[] args) 
  {
 
    // Given array 
    int arr[] = { 1, 2, 3, 4 }; 
 
    // Given K 
    int K = 2; 
 
    // Size of the array 
    int N = arr.length; 
 
    // Prints all possible 
    // splits into subsets 
    partKSubsets(arr, N, K); 
  }
}
 
// This code is contributed by offbeat

Python3

# Python 3 program for the above approach 
 
# arr: Store input array 
# i: Stores current index of arr 
# N: Stores length of arr 
# K: Stores count of subsets 
# nos: Stores count of feasible subsets formed 
# v: Store K subsets of the given array 
 
# Utility function to find all possible 
# ways to split array into K subsets 
def PartitionSub(arr, i, N, K, nos, v):
   
    # If count of elements in K subsets 
    # are greater than or equal to N 
    if (i >= N):
       
        # If count of subsets 
        # formed is equal to K 
        if (nos == K):
           
            # Print K subsets by splitting 
            # array into K subsets 
            for x in range(len(v)):
                print("{ ", end = "") 
 
                # Print current subset 
                for y in range(len(v[x])):
                    print(v[x][y], end = "") 
 
                    # If current element is the last 
                    # element of the subset 
                    if (y == len(v[x]) - 1):
                        print(" ", end = "")
 
                    # Otherwise 
                    else:
                        print(", ", end = "")
 
                if (x == len(v) - 1):
                    print("}", end = "") 
                 
                else:
                    print("}, ", end = "") 
            print("\n", end = "")
        return
    for j in range(K):
       
        # If any subset is occupied, 
        # then push the element 
        # in that first 
        if (len(v[j]) > 0):
            v[j].append(arr[i]) 
 
            # Recursively do the same 
            # for remaining elements 
            PartitionSub(arr, i + 1, N, K, nos, v)
             
            # Backtrack 
            v[j].remove(v[j][len(v[j]) - 1])
 
        # Otherwise, push it in an empty 
        # subset and increase the 
        # subset count by 1 
        else:
            v[j].append(arr[i]) 
            PartitionSub(arr, i + 1, N, K, nos + 1, v) 
            v[j].remove(v[j][len(v[j]) - 1]) 
 
            # Break to avoid the case of going in 
            # other empty subsets, if available, 
            # and forming the same combination 
            break
 
# Function to find all possible ways to 
# split array into K subsets 
def partKSubsets(arr, N, K):
   
    # Stores K subset by splitting array 
    # into K subsets 
    v = [[] for i in range(K)] 
 
    # Size of each subset must 
    # be less than the number of elements 
    if (K == 0 or K > N):
        print("Not Possible", end = "") 
    else:
        print("The Subset Combinations are: ") 
        PartitionSub(arr, 0, N, K, 0, v)
 
# Driver Code 
if __name__ == '__main__':
   
    # Given array 
    arr =  [1, 2, 3, 4] 
 
    # Given K 
    K = 2
 
    # Size of the array 
    N = len(arr) 
 
    # Prints all possible 
    # splits into subsets 
    partKSubsets(arr, N, K)
     
    # This code is contributed by bgangwar59.

C#

// C# program for the above approach 
using System;
using System.Collections.Generic; 
class GFG
{
 
  // arr: Store input array 
  // i: Stores current index of arr 
  // N: Stores length of arr 
  // K: Stores count of subsets 
  // nos: Stores count of feasible subsets formed 
  // v: Store K subsets of the given array 
 
  // Utility function to find all possible 
  // ways to split array into K subsets 
  static void PartitionSub(int []arr, int i, 
                           int N, int K, int nos, 
                           List<List<int>>v) 
{ 
 
  // If count of elements in K subsets 
  // are greater than or equal to N 
  if (i >= N) { 
 
    // If count of subsets 
    // formed is equal to K 
    if (nos == K) { 
 
      // Print K subsets by splitting 
      // array into K subsets 
      for (int x = 0; x < v.Count; x++) { 
 
        Console.Write("{ "); 
 
        // Print current subset 
        for (int y = 0; y < v[x].Count; y++) { 
          Console.Write(v[x][y]); 
 
          // If current element is the last 
          // element of the subset 
          if (y == v[x].Count - 1) { 
 
            Console.Write(" "); 
          } 
 
          // Otherwise 
          else { 
 
            Console.Write(", "); 
          } 
        } 
 
        if (x == v.Count - 1) { 
 
          Console.Write("}"); 
        } 
        else { 
 
          Console.Write("}, "); 
        } 
      } 
      Console.Write("\n"); 
    } 
 
    return; 
  } 
 
  for (int j = 0; j < K; j++) { 
 
    // If any subset is occupied, 
    // then push the element 
    // in that first 
    if (v[j].Count > 0) { 
      v[j].Add(arr[i]); 
 
      // Recursively do the same 
      // for remaining elements 
      PartitionSub(arr, i + 1, N, K, nos, v); 
 
      // Backtrack
      v[j].RemoveAt(v[j].Count - 1);
    } 
 
    // Otherwise, push it in an empty 
    // subset and increase the 
    // subset count by 1 
    else { 
 
      v[j].Add(arr[i]); 
      PartitionSub(arr, i + 1, N, K, nos + 1, v); 
      v[j].RemoveAt(v[j].Count - 1);
 
      // Break to avoid the case of going in 
      // other empty subsets, if available, 
      // and forming the same combination 
      break; 
    } 
  } 
} 
 
 // Function to find all possible ways to 
 // split array into K subsets 
 static void partKSubsets(int []arr, int N, int K) 
 { 
 
   // Stores K subset by splitting array 
   // into K subsets 
   List<List<int> > v = new List<List<int>>();
   for(int i=0;i<K;i++)
     v.Add(new List<int>()); 
 
   // Size of each subset must 
   // be less than the number of elements 
   if (K == 0 || K > N) { 
 
     Console.WriteLine("Not Possible"); 
   } 
   else { 
 
     Console.WriteLine("The Subset Combinations are: "); 
     PartitionSub(arr, 0, N, K, 0, v); 
   } 
 } 
 
 // Driver Code 
 public static void Main() 
 { 
 
   // Given array 
   int []arr = {1, 2, 3, 4}; 
 
   // Given K 
   int K = 2; 
 
   // Size of the array 
   int N = arr.Length; 
 
   // Prints all possible 
   // splits into subsets 
   partKSubsets(arr, N, K); 
 } 
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
    // Javascript program for above approach
     
    // arr: Store input array
    // i: Stores current index of arr
    // N: Stores length of arr
    // K: Stores count of subsets
    // nos: Stores count of feasible subsets formed
    // v: Store K subsets of the given array
 
    // Utility function to find all possible
    // ways to split array into K subsets
    function PartitionSub(arr, i, N, K, nos, v)
    {
 
      // If count of elements in K subsets
      // are greater than or equal to N
      if (i >= N)
      {
 
        // If count of subsets
        // formed is equal to K
        if (nos == K)
        {
 
          // Print K subsets by splitting
          // array into K subsets
          for (let x = 0; x < v.length; x++)
          {
 
            document.write("{ ");
 
            // Print current subset
            for (let y = 0; y < v[x].length; y++)
            {
              document.write(v[x][y]);
 
              // If current element is the last
              // element of the subset
              if (y == v[x].length - 1)
              {
                document.write(" ");
              }
 
              // Otherwise
              else
              {
                document.write(", ");
              }
            }
 
            if (x == v.length - 1)
            {
              document.write("}");
            }
            else
            {
              document.write("}, ");
            }
          }
          document.write("</br>");
        }
        return;
      }
 
      for (let j = 0; j < K; j++)
      {
 
        // If any subset is occupied,
        // then push the element
        // in that first
        if (v[j].length > 0)
        {
          v[j].push(arr[i]);
 
          // Recursively do the same
          // for remaining elements
          PartitionSub(arr, i + 1, N, K, nos, v);
 
          // Backtrack
          v[j].pop();
        }
 
        // Otherwise, push it in an empty
        // subset and increase the
        // subset count by 1
        else
        {
 
          v[j].push(arr[i]);
          PartitionSub(arr, i + 1, N, K, nos + 1, v);
          v[j].pop();
 
          // Break to avoid the case of going in
          // other empty subsets, if available,
          // and forming the same combination
          break;
        }
      }
    }
 
    // Function to find all possible ways to
    // split array into K subsets
    function partKSubsets(arr, N, K)
    {
 
      // Stores K subset by splitting array
      // into K subsets
      let v = [];
 
      for(let i = 0; i < K; i++)
        v.push([]);
 
      // Size of each subset must
      // be less than the number of elements
      if (K == 0 || K > N)
      {
        document.write("Not Possible" + "</br>");
      }
      else
      {
        document.write("The Subset Combinations are: " + "</br>");
        PartitionSub(arr, 0, N, K, 0, v);
      }
    }
     
    // Given array
    let arr = [ 1, 2, 3, 4 ];
  
    // Given K
    let K = 2;
  
    // Size of the array
    let N = arr.length;
  
    // Prints all possible
    // splits into subsets
    partKSubsets(arr, N, K);
 
// This code is contributed by decode2207.
</script>

Output

The Subset Combinations are: 
{ 1, 2, 3 }, { 4 }
{ 1, 2, 4 }, { 3 }
{ 1, 2 }, { 3, 4 }
{ 1, 3, 4 }, { 2 }
{ 1, 3 }, { 2, 4 }
{ 1, 4 }, { 2, 3 }
{ 1 }, { 2, 3, 4 }

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

1 COMMENT

Minimum groups to split Array such that their each pair value difference and position difference are same – Neveropen Tech 19 August 2025 At 11:55 am

[…] Approach: The simplest approach is, split the array into K subsets for every integer K less than or equal to N, and then check if all the subsets of the array satisfy […]

Log in to leave a comment

Print all possible ways to split an array into K subsets

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

1 COMMENT

LEAVE A REPLY Cancel reply

Most Popular

7 Chrome tips I picked up from Reddit — and now I feel lost without them

The Samsung One UI feature I forgot about — and fell back in love with

The Pixel Buds Pro 2 upgrades are nice — but not game-changing

Samsung preps ‘new’ Galaxy AI features for One UI 8.5

EDITOR PICKS

7 Chrome tips I picked up from Reddit — and now I feel lost without them

The Samsung One UI feature I forgot about — and fell back in love with

The Pixel Buds Pro 2 upgrades are nice — but not game-changing

POPULAR POSTS

7 Chrome tips I picked up from Reddit — and now I feel lost without them

The Samsung One UI feature I forgot about — and fell back in love with

The Pixel Buds Pro 2 upgrades are nice — but not game-changing

POPULAR CATEGORY

ABOUT US

FOLLOW US