How to Generate Permutations of an Array with Repetition in Java

Question

How can I generate permutations of an array, allowing for repetition, using Java?

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums, int repeatTime) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<Integer>(), nums, repeatTime);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int repeatTime) {
        if (tempList.size() == repeatTime) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int num : nums) {
                tempList.add(num);
                backtrack(result, tempList, nums, repeatTime);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

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

Answer

Generating permutations of an array with repetition in Java can be achieved through a recursive approach using backtracking. This allows us to explore all possible combinations of the elements of the array, given a specified length for the permutations.

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums, int repeatTime) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<Integer>(), nums, repeatTime);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int repeatTime) {
        if (tempList.size() == repeatTime) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int num : nums) {
                tempList.add(num);
                backtrack(result, tempList, nums, repeatTime);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

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

Causes

Understanding that repetition allows the same element to appear multiple times in combinations.
Familiarity with recursive algorithms and backtracking techniques.

Solutions

Implement a recursive function to generate permutations.
At each recursive call, add elements to the current permutation and track the size until it reaches the desired length.
Remove the last added element after exploring one level of recursion to backtrack.

Common Mistakes

Mistake: Not considering the base case properly in recursion.

Solution: Ensure the recursion stops when the length of the current permutation matches the desired length.

Mistake: Failing to reset the state after each recursion step.

Solution: Always remove the last added element after exploring one possibility to avoid incorrect states.

Helpers

Java permutations with repetition
generate permutations Java
Java backtracking
recursive permutations
integer array permutations Java