Count ways to select N pairs of candies of distinct colors (Dynamic Programming + Bitmasking)
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 ith red candy and jth 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 coloursint 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 Codeint 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 coloursstatic 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 Codepublic 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 coloursdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{ // Function to count ways to select N distinct// pairs of candies with different coloursstatic 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 Codepublic 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 coloursfunction 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:
3
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 jth bit of mask checks if jth blue candy is available for selecting the current pair or not.
The recurrence relation to solving the problem is as follows:
If Kth 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 2N – 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 2N-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][2n-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 colorsint 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 colorsdef 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 Codeif __name__ == "__main__": n = 3 mat = [[0, 1, 1], [1, 0, 1], [1, 1, 1]] print(numOfWays(mat, n)) |
C#
// C# program to implement above approachusing 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:
3
Time Complexity:O(N2 * 2N)
Auxiliary Space: O(N * 2N)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
