ASSIGN - Assignments - SPOJ Solution C++

Problem Link : ASSIGN

 

Hint : DP with Bitmasking

 

C++ Solution :

 

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
 
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		ll size=pow(2,n);
		ll dp[size];
		memset(dp,0,sizeof(dp));
		bool arr[n][n];
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				cin>>arr[i][j];
		}
		dp[0]=1;
		int cnt;
		for(int i=0;i<size;i++)
		{
			cnt=__builtin_popcount(i);
			for(int j=0;j<n;j++)
				if(!(i&(1<<j)) && arr[cnt][j])
					dp[i|(1<<j)]+=dp[i];
		}
 
		cout<<dp[size-1]<<"\n";
	}
} 

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.