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!

Answer 1

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);
    }
}