Permutations
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Permutations * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Permutations * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an integer array A of size N (containing unique numbers), return all possible * permutations. * * Definition: * A permutation is an arrangement of all members of a sequence into a order. * For N elements, there are N! (N factorial) possible permutations. * * Constraints: * - No two entries in the output sequence should be the same. * - Assume all numbers in the input collection are unique. * - DO NOT use library functions (e.g., Collections.shuffle, next_permutation). * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let P(index) be a function that generates permutations for the suffix of the array * starting at 'index'. * * Backtracking Strategy (Swap Method): * The idea is to determine which element should be placed at the current 'index'. * * Algorithm: * 1. Iterate 'i' from 'index' to N-1. * 2. Swap A[index] with A[i]. * (This places the element originally at A[i] into the current position 'index', * effectively "fixing" it there). * 3. Recursively call P(index + 1) to generate permutations for the rest of the array. * 4. Backtrack: Swap A[index] with A[i] again to restore the original state of the array * (Backtracking step). * * Base Case: * If index == N: * All positions are fixed. The current state of array A is a valid permutation. * Add a copy of A to the result list. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= N <= 9 * * Time Complexity: * O(N * N!) * - There are N! permutations. * - For each permutation, we take O(N) time to copy the array into the result list. * - For N=9, 9! = 362,880. Total ops ~ 3.2 million, which fits easily in 1 sec. * * Space Complexity: * O(N * N!) - To store the result. * O(N) - Recursion stack depth. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - Integer Array A. * * Output: * - A list of lists (2D array) containing all permutations. * * --------------------- * 5. Examples * --------------------- * Input: A = [1, 2, 3] * * Level 0 (index=0): * - Swap(0,0) -> [1, 2, 3]. Recurse(1). * Level 1 (index=1): * - Swap(1,1) -> [1, 2, 3]. Recurse(2) -> Add [1, 2, 3] * - Swap(1,2) -> [1, 3, 2]. Recurse(2) -> Add [1, 3, 2] * - Backtrack. * - Swap(0,1) -> [2, 1, 3]. Recurse(1)... * - Swap(0,2) -> [3, 2, 1]. Recurse(1)... * * Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]] * * ============================================================================================ */
public class Permutations { public int solve(int A) { // TODO: Implement solution return 0; }
public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> input1) {
return new ArrayList<>();
}
}