Permutations - LeetCode Solution in Java

1. Introduction

The "Permutations" problem is about generating all possible arrangements of a given set of distinct integers. This problem is a classic example of using backtracking to explore all possible combinations.

2. Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

3. Solution Steps

1. Utilize backtracking to generate permutations.

2. Start with an empty tempList to hold the current permutation.

3. When the size of tempList equals the size of nums, add it to the result.

4. Iterate through the nums array.

5. If an element is already in tempList, skip it.

6. Otherwise, add the element to tempList and continue the backtracking process.

7. After backtracking, remove the last element to make room for the next possibility.

4. Solution in Java

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

private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
    if (tempList.size() == nums.length) {
        result.add(new ArrayList<>(tempList));
    } else {
        for (int i = 0; i < nums.length; i++) {
            if (tempList.contains(nums[i])) continue; // element already exists, skip
            tempList.add(nums[i]);
            backtrack(result, tempList, nums);
            tempList.remove(tempList.size() - 1); // remove last element for next iteration
        }
    }
}

This solution uses a backtracking approach to explore all possible permutations of the given integers, systematically building up each permutation and backtracking as needed to explore all different combinations.

Explanation:

1. The backtrack method is designed to generate permutations.

2. When tempList has the same size as nums, it represents a complete permutation and is added to result.

3. The method iterates over nums, checking if an element is already included in tempList.

4. If not, the element is added, and backtracking continues to build the permutation.

5. After exploring a path, the last element is removed (tempList.remove(tempList.size() - 1)) to backtrack and explore other paths.

6. This process repeats until all permutations are generated.