Find All Combinations of Perfect Squares that Sum up to N with Duplicates

Approach

Here, we will use a recursive as well as backtracking approach to solve the problem.

Follow the below steps to implement the solution.

• First, find all perfect squares less than the given N and store them in an array.
• Then use a recursive function to find the combinations that sum up to N using the list of the perfect squares.
• For any particular index, include the perfect square at that index in the combination and make a recursive call at the same index as repetition of the same number is allowed. Otherwise, don’t include the number at that index and move to the next index.
• When summation exceeds N or list of squares, return from the recursive function.
•  If summation equals N, then print that combination of numbers.

Code

#include<bits/stdc++.h> using namespace std; //function for finding the combinations of perfect squares that sum up to N void combinations(vector<int> perfectSquares,int idx,int n,vector<int> combination) { // summation exceeds n or list of squares if(n<0 || idx==perfectSquares.size() ) { return; } //summation equals to n if(n==0) { //print the combination for(int e:combination) { cout<<e<<" "; } cout<<endl; return; } //not include the element at the current index combinations(perfectSquares,idx+1,n,combination); //include the perfect square at the current index combination.push_back(perfectSquares[idx]); //recursive call for the same index combinations(perfectSquares,idx,n-perfectSquares[idx],combination); //back track combination.pop_back(); return; } void sumOfsqures(int n) {    vector<int> perfectSquares;    //storing perfect squares less than n       int k=(int)(sqrt(n));    for(int i=1;i<=k;i++)    {    perfectSquares.push_back(i*i); } vector<int> combination;    combinations(perfectSquares,0,n,combination); } int main() { int n=6; sumOfsqures(n); } You can also try this code with Online C++ Compiler Run Code

Output

Complexity analysis

In the worst-case time complexity of the above implementation is O(n*2n) where n is the given number.

Here, space complexity is O(n) as we need extra space for storing the list of perfect squares as well as the combinations of perfect squares.

FAQs

1. What is backtracking?
   Backtracking is a recursive approach to solving a problem. The algorithm tries to find a sequence path to the solution and it can backtrack at some check points if no feasible solution can be found on that sequence path.
    
2. Mention some applications of backtracking?
   The backtracking algorithm is used to solve many famous problems such as the N queen problem, finding the Hamilton path in a graph, rat and maze problem, sudoku solver, etc.

Key Takeaways

This article covered how to find all combinations of perfect squares that sum up to N with duplicates using the backtracking approach.

We highly recommend going through the articles on backtracking to grasp the concepts clearly.
Check out this problem - Subarray Sum Divisible By K

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!