Data Modelling & AI Data Structure & Algorithm

Count ways to select N pairs of candies of distinct colors (Dynamic Programming + Bitmasking)

23 June 2025

0

Given an integer N representing the number of red and blue candies and a matrix mat[][] of size N * N, where mat[i][j] = 1 represents the existence of a pair between i^th red candy and j^th blue candy, the task is to find the count of ways to select N pairs of candies such that each pair contains distinct candies of different colors.

Examples:

Input: N = 2, mat[][] = { { 1, 1 }, { 1, 1 } }
Output: 2
Explanation:
Possible ways to select N (= 2) pairs of candies are { { (1, 1), (2, 2) }, { (1, 2), (2, 1) } }.
Therefore, the required output is 2.

Input: N = 3, mat[][] = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } }
Output: 3
Explanation:
Possible ways to select N (= 3) pairs of candies are: { { (1, 2), (2, 1), (3, 3) }, { (1, 2), (2, 3), (3, 1) }, { (1, 3), (2, 1), (3, 2) } }
Therefore, the required output is 2.

Naive Approach: The simplest approach to solve this problem is to generate all possible permutations of N pairs containing distinct candies of different colors. Finally, print the count obtained.

Below is the implementation of the above approach:

C++14

// C++14 program to implement 
// the above approach 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count ways to select N distinct
// pairs of candies with different colours
int numOfWays(vector<vector<int>> a, int n,
                 int i, set<int> &blue)
{
     
    // If n pairs are selected
    if (i == n)
        return 1;
 
    // Stores count of ways
    // to select the i-th pair
    int count = 0;
 
    // Iterate over the range [0, n]
    for(int j = 0; j < n; j++)
    {
         
        // If pair (i, j) is not included
        if (a[i][j] == 1 && blue.find(j) == blue.end())
        {
            blue.insert(j);
            count += numOfWays(a, n, i + 1, blue);
            blue.erase(j);
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    int n = 3;
    vector<vector<int>> mat = { { 0, 1, 1 },
                                { 1, 0, 1 },
                                { 1, 1, 1 } };
    set<int> mpp;
     
    cout << (numOfWays(mat, n, 0, mpp));
}
 
// This code is contributed by mohit kumar 29

Java

// Java program to implement 
// the above approach 
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to count ways to select N distinct
// pairs of candies with different colours
static int numOfWays(int a[][], int n, int i,
                     HashSet<Integer> blue)
{
     
    // If n pairs are selected
    if (i == n)
        return 1;
 
    // Stores count of ways
    // to select the i-th pair
    int count = 0;
 
    // Iterate over the range [0, n]
    for(int j = 0; j < n; j++) 
    {
         
        // If pair (i, j) is not included
        if (a[i][j] == 1 && !blue.contains(j)) 
        {
            blue.add(j);
            count += numOfWays(a, n, i + 1, blue);
            blue.remove(j);
        }
    }
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 3;
    int mat[][] = { { 0, 1, 1 }, 
                    { 1, 0, 1 }, 
                    { 1, 1, 1 } };
    HashSet<Integer> mpp = new HashSet<>();
 
    System.out.println((numOfWays(mat, n, 0, mpp)));
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program to implement
# the above approach
 
 
# Function to count ways to select N distinct 
# pairs of candies with different colours
def numOfWays(a, n, i = 0, blue = []):
 
    # If n pairs are selected
    if i == n:
        return 1
 
    # Stores count of ways 
    # to select the i-th pair
    count = 0
 
    # Iterate over the range [0, n]
    for j in range(n):
 
        # If pair (i, j) is not included
        if mat[i][j] == 1 and j not in blue:
            count += numOfWays(mat, n, i + 1, 
                                blue + [j])
                                 
    return count
 
# Driver Code
if __name__ == "__main__":
    n = 3
    mat = [ [0, 1, 1],
            [1, 0, 1], 
            [1, 1, 1] ]
    print(numOfWays(mat, n))

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to count ways to select N distinct
// pairs of candies with different colours
static int numOfWays(int[,] a, int n, int i,
                     HashSet<int> blue)
{
     
    // If n pairs are selected
    if (i == n)
        return 1;
 
    // Stores count of ways
    // to select the i-th pair
    int count = 0;
 
    // Iterate over the range [0, n]
    for(int j = 0; j < n; j++)
    {
         
        // If pair (i, j) is not included
        if (a[i, j] == 1 && !blue.Contains(j))
        {
            blue.Add(j);
            count += numOfWays(a, n, i + 1, blue);
            blue.Remove(j);
        }
    }
    return count;
}
 
// Driver Code
public static void Main()
{
    int n = 3;
    int[,] mat = { { 0, 1, 1 },
                   { 1, 0, 1 }, 
                   { 1, 1, 1 } };
    HashSet<int> mpp = new HashSet<int>();
 
    Console.WriteLine((numOfWays(mat, n, 0, mpp)));
}
}
 
// This code is contributed by ukasp

Javascript

<script>
// Javascript program to implement
// the above approach
 
// Function to count ways to select N distinct
// pairs of candies with different colours
function numOfWays(a, n, i, blue)
{
     
    // If n pairs are selected
    if (i == n)
        return 1;
 
    // Stores count of ways
    // to select the i-th pair
    let count = 0;
 
    // Iterate over the range [0, n]
    for(let j = 0; j < n; j++)
    {
         
        // If pair (i, j) is not included
        if (a[i][j] == 1 && !blue.has(j))
        {
            blue.add(j);
            count += numOfWays(a, n, i + 1, blue);
            blue.delete(j);
        }
    }
    return count;
}
 
// Driver Code
 
    let n = 3;
    let mat = [ [ 0, 1, 1 ],
                [ 1, 0, 1 ],
                [ 1, 1, 1 ] ];
    let mpp = new Set();
     
     
    document.write(numOfWays(mat, n, 0, mpp));
 
// This code is contributed by _saurabh_jaiswal
</script>

Output:

Time complexity: O(N!)
Auxiliary Space: O(N) where N is recursion stack space

Efficient Approach: The above approach can be optimized for Dynamic programming with Bit masking. Instead of generating all permutations of N blue candies, for every red candy, use a mask, where j^th bit of mask checks if j^th blue candy is available for selecting the current pair or not.
The recurrence relation to solving the problem is as follows:

If K^th bit of mask is unset and mat[i][k] = 1:
dp[i + 1][j | (1 << k)] += dp[i][j]

where, (j | (1 << k)) marks the kth blue candy as selected.
dp[i][j] = Count of ways to make pairs between i red candy and N blue candies, where j is a permutation of N bit number ranging from 0 to 2^N – 1).

Follow the steps below to solve the problem:

Initialize a 2D array, say dp[][], where dp[i][j] stores the count of ways to make pairs between i red candies and N blue candies. j represents a permutation of N bit number ranging from 0 to 2^N-1.
Use the above recurrence relation and fill all possible dp states of the recurrence relation.
Finally, print the dp state where there are N red candies and N blue candies are selected, i.e. dp[i][2ⁿ-1].

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
 
#include <iostream>
#include <cstring>
using namespace std;
 
// Function to count ways to select N distinct
// pairs of candies with different colors
int numOfWays(int a[][100], int n) 
{
   
    // dp[i][j]: Stores count of ways to make
    // pairs between i red candies and N blue candies
    int dp[100][1 << n];
 
    memset(dp, 0, sizeof(dp));
 
    // If there is no red and blue candy,
    // the count of ways to make n pairs is 1
    dp[0][0] = 1;
 
    // i: Stores count of red candy
    for (int i = 0; i < n; i++) {
 
        // j generates a permutation of blue
        // candy of selected / not selected
        // as a binary number with n bits
        for (int j = 0; j < (1 << n); j++) {
 
            if (dp[i][j] == 0) {
                continue;
            }
 
            // Iterate over the range [0, n]
            for (int k = 0; k < n; k++) {
 
                // Create a mask with only
                // the k-th bit as set
                int mask = (1 << k);
 
                // If Kth bit of mask is
                // unset and mat[i][k] = 1
                if ((mask & j) == 0 && a[i][k] == 1) {
                    dp[i + 1][j | mask] += dp[i][j];
                }
            }
        }
    }
 
    // Return the dp states, where n red
    // and n blue candies are selected
    return dp[n][(1 << n) - 1];
}
 
int main()
{
    int n = 3;
    int mat[100][100] = {
    {0, 1, 1},
    {1, 0, 1},
    {1, 1, 1}
    };
    cout<<numOfWays(mat, n);
    return 0;
}
 
// This code is contributed by phasing17

Java

import java.util.Arrays;
 
public class Main {
 
  // Function to count ways to select N distinct
  // pairs of candies with different colors
  static int numOfWays(int[][] a, int n) {
 
    // dp[i][j]: Stores count of ways to make
    // pairs between i red candies and N blue candies
    int[][] dp = new int[n + 1][1 << n + 1];
 
    // If there is no red and blue candy,
    // the count of ways to make n pairs is 1
    dp[0][0] = 1;
 
    // i: Stores count of red candy
    for (int i = 0; i < n; i++) {
 
      // j generates a permutation of blue
      // candy of selected / not selected
      // as a binary number with n bits
      for (int j = 0; j < (1 << n); j++) {
 
        if (dp[i][j] == 0) {
          continue;
        }
 
        // Iterate over the range [0, n]
        for (int k = 0; k < n; k++) {
 
          // Create a mask with only
          // the k-th bit as set
          int mask = (1 << k);
 
          // If Kth bit of mask is
          // unset and mat[i][k] = 1
          if ((mask & j) == 0 && a[i][k] == 1) {
            dp[i + 1][j | mask] += dp[i][j];
          }
        }
      }
    }
 
    // Return the dp states, where n red
    // and n blue candies are selected
    return dp[n][(1 << n) - 1];
  }
 
  public static void main(String[] args) {
    int n = 3;
    int[][] mat = new int[][] {
      {0, 1, 1},
      {1, 0, 1},
      {1, 1, 1}
    };
    System.out.println(numOfWays(mat, n));
  }
}
 
// This code is contributed by phasing17.

Python3

# Python program to implement
# the above approach
  
  
# Function to count ways to select N distinct 
# pairs of candies with different colors
def numOfWays(a, n):
 
 
    # dp[i][j]: Stores count of ways to make
    # pairs between i red candies and N blue candies
    dp = [[0]*((1 << n)+1) for _ in range(n + 1)]
 
    # If there is no red and blue candy,
    # the count of ways to make n pairs is 1
    dp[0][0] = 1
 
    # i: Stores count of red candy
    for i in range(n):
 
        # j generates a permutation of blue
        # candy of selected / not selected 
        # as a binary number with n bits
        for j in range(1 << n):
 
            if dp[i][j] == 0:
                continue
    
            # Iterate over the range [0, n]    
            for k in range(n):
 
                # Create a mask with only
                # the k-th bit as set
                mask = 1 << k
                 
                # If Kth bit of mask is
                # unset  and mat[i][k] = 1
                if not(mask & j) and a[i][k]:
                    dp[i + 1][j | mask] += dp[i][j]
                     
         
                     
    # Return the dp states, where n red
    # and n blue candies are selected
    return dp[n][(1 << n)-1]
 
 
 
# Driver Code
if __name__ == "__main__":
    n = 3
    mat = [[0, 1, 1],
           [1, 0, 1],
           [1, 1, 1]]
    print(numOfWays(mat, n))

C#

// C# program to implement above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to count ways to select N distinct 
  // pairs of candies with different colors
  static int numOfWays(int[][] a,int n){
 
 
    // dp[i][j]: Stores count of ways to make
    // pairs between i red candies and N blue candies
    int[][] dp = new int[n+1][];
    for(int i = 0 ; i <= n ; i++){
      dp[i] = new int[(1 << n)+1];
    }
 
    // If there is no red and blue candy,
    // the count of ways to make n pairs is 1
    dp[0][0] = 1;
 
    // i: Stores count of red candy
    for(int i = 0 ; i < n ; i++){
 
      // j generates a permutation of blue
      // candy of selected / not selected 
      // as a binary number with n bits
      for(int j = 0 ; j < (1 << n) ; j++){
 
        if (dp[i][j] == 0){
          continue;
        }
 
        // Iterate over the range [0, n] 
        for (int k = 0 ; k < n ; k++){
 
          // Create a mask with only
          // the k-th bit as set
          int mask = (1 << k);
 
          // If Kth bit of mask is
          // unset and mat[i][k] = 1
          if ((mask & j) == 0 && a[i][k] == 1){
            dp[i + 1][j | mask] += dp[i][j];
          }
        }
      }
    }
 
    // Return the dp states, where n red
    // and n blue candies are selected
    return dp[n][(1 << n)-1];
  }
 
  // Driver Code
  public static void Main(string[] args){
 
    int n = 3;
    int[][] mat = new int[3][];
    mat[0] = new int[]{0, 1, 1};
    mat[1] = new int[]{1, 0, 1};
    mat[2] = new int[]{1, 1, 1};
    Console.Write(numOfWays(mat, n));
 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

function numOfWays(a, n) {
 
    // dp[i][j]: Stores count of ways to make
    // pairs between i red candies and N blue candies
    let dp = Array.from({ length: n + 1 },
        () => Array.from({ length: (1 << n) + 1 }, () => 0));
 
    // If there is no red and blue candy,
    // the count of ways to make n pairs is 1
    dp[0][0] = 1;
 
    // i: Stores count of red candy
    for (let i = 0; i < n; i++) {
 
        // j generates a permutation of blue
        // candy of selected / not selected 
        // as a binary number with n bits
        for (let j = 0; j < (1 << n); j++) {
 
            if (dp[i][j] === 0) continue;
 
            // Iterate over the range [0, n]
            for (let k = 0; k < n; k++) {
 
                // Create a mask with only
                // the k-th bit as set
                let mask = 1 << k;
 
                // If Kth bit of mask is
                // unset  and mat[i][k] = 1
                if (!(mask & j) && a[i][k]) {
                    dp[i + 1][j | mask] += dp[i][j];
                }
            }
        }
    }
 
    // Return the dp states, where n red
    // and n blue candies are selected
    return dp[n][(1 << n) - 1];
}
 
let n = 3;
let mat =  [[0, 1, 1],
           [1, 0, 1],
           [1, 1, 1]]
 
 console.log(numOfWays(mat, n))

Output:

Time Complexity:O(N² * 2^N)
Auxiliary Space: O(N * 2^N)

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!

3 COMMENTS

Model Spoor Club Achterhoek 17 November 2025 At 4:00 am

… [Trackback]

[…] Here you will find 10696 additional Info on that Topic: geeksforgeeks.org/count-ways-to-select-n-pairs-of-candies-of-distinct-colors-dynamic-programming-bitmasking/ […]

Log in to leave a comment
fish 3 February 2026 At 2:48 am

… [Trackback]

[…] Find More on that Topic: geeksforgeeks.org/count-ways-to-select-n-pairs-of-candies-of-distinct-colors-dynamic-programming-bitmasking/ […]

Log in to leave a comment
À la carte & pfannkuchen 6 June 2026 At 7:34 pm

… [Trackback]

[…] Find More on that Topic: geeksforgeeks.org/count-ways-to-select-n-pairs-of-candies-of-distinct-colors-dynamic-programming-bitmasking/ […]

Log in to leave a comment

Count ways to select N pairs of candies of distinct colors (Dynamic Programming + Bitmasking)

C++14

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

3 COMMENTS

LEAVE A REPLY Cancel reply

Most Popular

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

EDITOR PICKS

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

POPULAR POSTS

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

POPULAR CATEGORY

ABOUT US

FOLLOW US