Understanding Full Permutations and Backtracking in Java

Permutation (全排列) refers to arranging n distinct elements; when selecting m (m≤n) elements in a specific order it forms a permutation, and when m=n it is a full permutation.

For example, the array [1,2,3] has six possible full permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

The interview problem asks: given a sequence of distinct numbers, return all possible permutations.

The solution uses a depth‑first search (DFS) backtracking approach, exploring each position sequentially and undoing choices when backtracking to previous levels.

Key steps of the algorithm:

Choose a number for the first position (three possibilities for [1,2,3]).

For the second position, choose among the remaining numbers (two possibilities).

For the third position, only one number remains.

When a full permutation is formed, add it to the result list.

After exploring a branch, remove the last chosen number to backtrack.

The Java implementation (not optimized for performance) demonstrates these ideas:

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(nums, new ArrayList<>());
        return ans;
    }
    private void dfs(int[] nums, List<Integer> tmp) {
        System.out.println(Arrays.toString(nums) + "," + tmp);
        if (tmp.size() == nums.length) {
            ans.add(new ArrayList<>(tmp));
        } else {
            for (int num : nums) {
                if (!tmp.contains(num)) {
                    tmp.add(num);
                    dfs(nums, tmp);
                    tmp.remove(tmp.size() - 1);
                }
            }
        }
    }
}

When run with nums = [1,2,3], the program prints the exploration process, showing how choices are made and undone at each recursion level.

The backtracking technique, also known as depth‑first search with backtrack, is a fundamental algorithmic strategy for combinatorial problems such as generating permutations.

In summary, the article provides a clear, step‑by‑step explanation of the permutation problem, its relation to DFS backtracking, and a straightforward Java solution suitable for interview preparation.