Permutations - Java Solution

1. Introduction

In this blog post, we explore the problem of generating all possible permutations of a set of distinct integers. This problem is a fundamental example of combinatorics and recursion in computer science, often encountered in algorithm design and coding interviews.

Problem

Given an array nums of distinct integers, the goal is to return all possible permutations of these numbers. The permutations can be returned in any order.

2. Solution Steps

1. Use a recursive approach to build permutations.

2. At each step, choose an element for the current position and recursively permute the remaining elements.

3. Swap elements back to maintain the array's integrity for further permutations.

4. Base condition: If the current position is the last element, add the permutation to the result.

5. Return the list of permutations.

3. Code Program

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

public class Permutations {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3};
        System.out.println(permute(nums1)); // Example 1
        int[] nums2 = {0, 1};
        System.out.println(permute(nums2)); // Example 2
        int[] nums3 = {1};
        System.out.println(permute(nums3)); // Example 3
    }

    // Function to generate all permutations of nums
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, nums, 0);
        return list;
    }

    // Helper function for backtracking
    private static void backtrack(List<List<Integer>> list, int[] nums, int start) {
        if (start == nums.length) {
            List<Integer> tempList = new ArrayList<>();
            for (int num : nums) {
                tempList.add(num);
            }
            list.add(tempList);
        } else {
            for (int i = start; i < nums.length; i++) {
                swap(nums, start, i); // Swap the elements
                backtrack(list, nums, start + 1); // Recurse for the next element
                swap(nums, start, i); // Swap back to backtrack
            }
        }
    }

    // Utility function to swap elements in the array
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Output:

Example 1: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2: [[0,1],[1,0]]
Example 3: [[1]]

Explanation:

1. permute: The main function initiates the permutation process. It calls backtrack with the initial start index.

2. backtrack: A recursive helper function that generates permutations. It swaps elements to fix one element at the current position and then recursively permutes the remaining elements.

3. Swapping is done before and after the recursive call to ensure that the array's state is maintained for other permutations.

4. When the start index reaches the array's length, a permutation is complete and added to the result list.

5. The function returns a list of all possible permutations of the given numbers.