Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 22, 2022 by Ria Pathak

Concepts Used

Back Tracking

Difficulty Level

Medium

Problem Statement :

Given N integers print all possible combinations.

See original problem statement here

Solution Approach :

Introduction :

Idea is to swap all the values one-by-one and print all different combinations. In a set of n elements there are n! different permutations. For example, there are six permutations of the set {1,2,3}, namely (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).

Description :

We need to explore all the possible combinations which can be solved with backtracking.

Backtracking is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.

We will swap every index of the array and then break our problem into subproblems, by recursively calling our function for the next index, when the index becomes equal to the size of the array we print the current combination, every time we swap indices we make sure to revert the changes by swapping them back again to try another combinations (backtrack).

Algorithm :

backtrack() :

  1. If index == n, print the current combination.
  2. else, for every k= index to n-1 :
    • swap(index,k)
    • call backtrack(arr,index+1,n)
    • swap(index,k) , (Backtrack step).

Complexity Analysis :

Total number of permutations are, as discussed earlier, n!, and it takes O(n) time to print each permutation. Can you guess the final time complexity?

Solutions:

#include <stdio.h>
 
    void swap(int *a,int *b)
    {
      int temp = *a;
      *a = *b;
      *b = temp;
    }
 
    void backtracking(int a[],int i,int n)
    {
 
      if(i==n-1)
      {
        for(int i=0;i<n;i++)
         printf("%d ",a[i]);
        printf("\n");
        return;
      }
 
      for(int k=i;k<n;k++)
      {
        swap(&a[k],&a[i]);
 
        backtracking(a,i+1,n);
 
        swap(&a[k],&a[i]); //backtrack
      }
 
    }
 
    int main()
    {
      int n;
      scanf("%d",&n);
      int a[n];
      for(int i=0;i<n;i++)
       scanf("%d",&a[i]);
 
      backtracking(a,0,n);
 
      return 0;
    }
#include <bits/stdc++.h>
    using namespace std;

    void swap(int *a,int *b)
    {
      int temp = *a;
      *a = *b;
      *b = temp;
    }

    void backtracking(int a[],int i,int n)
    {
      if(i==n-1)
      {
        for(int i=0;i<n;i++)
         cout<<a[i]<<" ";
        cout<<endl;
        return;
      }

      for(int k=i;k<n;k++)
      {
        swap(&a[k],&a[i]);

        backtracking(a,i+1,n);

        swap(&a[k],&a[i]);


      }

    }

    int main()
    {
      int n;
      cin>>n;
      int a[n],ans[n];
      for(int i=0;i<n;i++)
       cin>>a[i];

      backtracking(a,0,n);


      return 0;
    }
import java.util.Scanner; 
    public class Main   
    {
        static void permute(int[] a, int k) 
        {
            if (k == a.length) 
            {
                for (int i = 0; i < a.length; i++) 
                {
                    System.out.print( a[i] + " ");
                }
                System.out.println();
            }  
            else  
            {
                for (int i = k; i < a.length; i++) 

                {

                    int temp = a[k];

                    a[k] = a[i];

                    a[i] = temp;
                    permute(a, k + 1);
                    temp = a[k];

                    a[k] = a[i];

                    a[i] = temp;   
                }
            } 
        } 
        public static void main(String args[]) 
        {   
            Scanner sc = new Scanner(System.in);

            int n = sc.nextInt();

            int[] sequence = new int[n];

            for (int i = 0; i < n; i++)
                sequence[i] = sc.nextInt();

            permute(sequence, 0);

            sc.close();  
        }   
    }
def backtracking(a, i, n):
	
	if i == n - 1:
	
		for i in range(n):
			print(a[i], end = " ")
	
		print()
		return

	for k in range(i, n):
		
		a[k], a[i] = a[i], a[k]
		backtracking(a, i + 1, n)
		a[k], a[i] = a[i], a[k]

n = int(input())
a = list(map(int,input().split()))
backtracking(a, 0, n)

[forminator_quiz id="2092"]

This article tried to discuss the concept of backtracking. Hope this blog helps you solve the problem based on backtracking . To practice more problems you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *