can someone tell me what is wrong with the code . It is not printing all the permutations of the array

Question

it is a common problem of backtracking.Here we have to print the possible permutations of an array of numbers. The code written by me:

import java.util.*;

public class Arraypermutations {
    public static void helper(List<List<Integer>> Array, List<Integer> permute, boolean done, List<Integer> nums){
         
        if (nums.size() == 0) {
            Array.add(new ArrayList<>(permute));
            return;
        }

        for(int i = 0; i < nums.size(); i++) {
            int currInt = nums.get(i);
            nums.remove(i);
            helper(Array, permute, permute.add(currInt), nums);
        }
    }

    public static List<List<Integer>> permute(int num[]){
        List<Integer> nums = new ArrayList<>();

        for (int i : num) {
            nums.add(i);
        }

        List<List<Integer>> Array = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        boolean done = false;
        helper(Array, permute, done, nums);
        return Array;
    }

    public static void main(String[] args) {
        int num[] = {1,2,3};   
        List<List<Integer>> Array = permute(num);
        System.out.println(Array);
    }

}

this would be expected answer of the code. [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] But my code is giving only [[1,2,3]]; as the answer. problem lies somewhere in the backtrcking of the code. But i dont understand it well; please help!

You should keep an eye of proper formatting (especially indentation, but also a consistent indentation *style*, you are intermixing Java conventions and Allman style) in your code, as is it is pretty hard to read. — Aconcagua, Aug 04 '23 at 09:03
[This question](https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation) might be pretty interesting for you – yes, it is C++, but you might still be able to read it. `std::next_permutation` does pretty much what you need here, you might adapt the algorithm and run it within a loop (instead of recursing). — Aconcagua, Aug 04 '23 at 09:11

score 0 · Answer 1 · answered Aug 04 '23 at 09:08

The issue in your code lies in the way you are backtracking and manipulating the nums list while iterating through it. When you're removing an element from the nums list during the iteration, it affects the indices of the remaining elements, leading to incorrect results.

Here's the corrected version of your code:

import java.util.*;

public class ArrayPermutations {
    public static void helper(List<List<Integer>> result, List<Integer> permute, List<Integer> nums) {
        if (nums.size() == 0) {
            result.add(new ArrayList<>(permute));
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            int currInt = nums.get(i);
            permute.add(currInt);
            nums.remove(i);
            helper(result, permute, nums);
            nums.add(i, currInt);
            permute.remove(permute.size() - 1);
        }
    }

    public static List<List<Integer>> permute(int[] num) {
        List<Integer> nums = new ArrayList<>();
        for (int i : num) {
            nums.add(i);
        }
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        helper(result, permute, nums);
        return result;
    }

    public static void main(String[] args) {
        int[] num = {1, 2, 3};
        List<List<Integer>> result = permute(num);
        System.out.println(result);
    }
}

score 0 · Accepted Answer · answered Aug 04 '23 at 09:08

Try this

import java.util.*;
public class ArrayPermutations {
    public static void helper(List<List<Integer>> result, List<Integer> current, List<Integer> nums) {
        if (nums.size() == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            int currInt = nums.get(i);
            nums.remove(i);
            current.add(currInt);

            helper(result, current, nums);

            current.remove(current.size() - 1);  // Backtrack: remove the last added element
            nums.add(i, currInt);  // Backtrack: restore the removed element at its original position
        }
    }

    public static List<List<Integer>> permute(int num[]) {
        List<Integer> nums = new ArrayList<>();
        for (int i : num) {
            nums.add(i);
        }
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        helper(result, current, nums);
        return result;
    }

    public static void main(String[] args) {
        int num[] = {1, 2, 3};
        List<List<Integer>> result = permute(num);
        System.out.println(result);
    }
}

score 0 · Answer 3 · edited Aug 09 '23 at 04:10

0

for (int i = 0; i < nums.size(); i++) {
    int currInt = nums.get(i);
    nums.remove(i);
    permute.add(currInt);
    helper(array, permute, nums);
    permute.remove(permute.size() - 1); 
    nums.add(i, currInt); 
}

Please modify your for loop and this might help to solve the problem.

edited Aug 09 '23 at 04:10

Abra

19,142
7
29
41

answered Aug 04 '23 at 09:10

Amal Rajesh

1
2

Ranjan · Answer 4 · 2023-08-09T06:22:44.493

Here my method calculation,

package com.example.demo;
import java.util.*;

public class Test {

    public static List<List<Integer>> permute(int num[]){
        List<Integer> nums = new ArrayList<>();
        for (int i : num) {
            nums.add(i);
        }
        List<List<Integer>> Array = new ArrayList<>();
        int maxPermutations = factorial(nums.size());
        while(maxPermutations>Array.size() ) {
             List<Integer> permute = new ArrayList<>(nums); 
                Collections.shuffle(permute);
                if (!Array.contains(permute)) {
                    Array.add(permute);
                }
        }
        return Array;
    }

    public static void main(String[] args) {
        int num[] = {1,2,3};   
        List<List<Integer>> Array = permute(num);
        System.out.println("Final arr:"+Array);
    }

    private static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

}

can someone tell me what is wrong with the code . It is not printing all the permutations of the array

4 Answers4