如何实现ArrayList<Integer>的非0开头全排列通用方法？

Hey there! I get exactly what you're dealing with—nested loops work for fixed small sizes, but they're totally useless when the list length can change. Recursive backtracking is the perfect tool here, since it dynamically adapts to any collection size while letting us enforce that "no leading zero" rule efficiently.

Here's the core approach: #

• Use backtracking to build permutations one element at a time
• Early pruning: Skip choosing 0 as the first element entirely, so we don't waste time generating invalid permutations just to filter them later
• Keep track of our current permutation path and the remaining elements we haven't used yet

Java Implementation (Works for Any List Size) #

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

public class ValidPermutations {
    public static List<List<Integer>> getValidPermutations(ArrayList<Integer> nums) {
        List<List<Integer>> validResults = new ArrayList<>();
        backtrack(new ArrayList<>(), new ArrayList<>(nums), validResults);
        return validResults;
    }

    private static void backtrack(List<Integer> currentPerm, List<Integer> remainingNums, List<List<Integer>> results) {
        // We've built a complete permutation—add it to results
        if (remainingNums.isEmpty()) {
            results.add(new ArrayList<>(currentPerm));
            return;
        }

        for (int i = 0; i < remainingNums.size(); i++) {
            Integer currentNum = remainingNums.get(i);
            
            // Prune invalid paths: skip 0 if it's the first element in the permutation
            if (currentPerm.isEmpty() && currentNum == 0) {
                continue;
            }

            // Choose the current number
            currentPerm.add(currentNum);
            // Create a new list of remaining numbers (remove the chosen one)
            List<Integer> updatedRemaining = new ArrayList<>(remainingNums);
            updatedRemaining.remove(i);
            // Recurse to build the rest of the permutation
            backtrack(currentPerm, updatedRemaining, results);
            // Undo the choice (backtrack) to try the next number
            currentPerm.remove(currentPerm.size() - 1);
        }
    }

    // Test with your example input
    public static void main(String[] args) {
        ArrayList<Integer> input = new ArrayList<>(List.of(0, 1, 2));
        List<List<Integer>> permutations = getValidPermutations(input);
        
        permutations.forEach(System.out::println);
        // Output will be:
        // [1, 2, 0]
        // [1, 0, 2]
        // [2, 0, 1]
        // [2, 1, 0]
    }
}

Key Details: #

1. Early Pruning: The check if (currentPerm.isEmpty() && currentNum == 0) ensures we never start a permutation with 0. This is way more efficient than generating all permutations first and then filtering out the invalid ones.
2. Backtracking Logic: We build permutations incrementally, add a number to our current path, recurse with the remaining numbers, then remove the number (undo the choice) to try the next option.
3. Handling Duplicates (Optional): If your input list might have duplicate integers (like [0,0,1]), you can add duplicate-handling logic to avoid duplicate permutations:
   • First sort the input list in the main method: nums.sort(Integer::compareTo);
   • Add this check inside the loop in the backtrack method:

     if (i > 0 && remainingNums.get(i).equals(remainingNums.get(i-1))) {
         continue;
     }
     

   This skips over identical adjacent elements once we've already processed them.

This method works for any size of ArrayList<Integer>—whether your list has 3 elements like your example, or 10, it'll generate all valid permutations without leading zeros.

内容的提问来源于stack exchange，提问作者JuanMartinez