All Unique 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: All Unique Permutations
* Group: 07. Recursion
*/
/
* ============================================================================================
* PROBLEM: All Unique Permutations
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given an array A of size N that might contain duplicates, return all possible unique permutations.
*
* Constraints:
* - No two entries in the output sequence should be the same.
* - DO NOT use library functions (e.g., next_permutation).
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Let P(current_permutation) be the recursive function.
* We need to fill positions 0 to N-1 with available numbers.
*
* Key Strategy:
* 1. Sort the Array:
* Sorting groups identical elements together (e.g., [1, 2, 1] -> [1, 1, 2]).
* This allows us to easily detect duplicates.
*
* 2. Visited Array:
* We use a boolean array visited[] to track which elements from the input are currently
* used in the partial permutation.
*
* 3. Handling Duplicates (The "Skip" Logic):
* When iterating through candidates to place at the current position:
* If A[i] == A[i-1], we must decide whether to use A[i].
*
* Rule: Only use A[i] if A[i-1] has already been used in the current recursion stack.
* Condition to SKIP:
* if (i > 0 && A[i] == A[i-1] && !visited[i-1]) continue;
*
* Why?
* - If visited[i-1] is false, it means we have just backtracked from using A[i-1] (or skipped it).
* - Starting a new permutation branch with A[i] (which has the same value) would produce
* the exact same set of permutations as the branch we just finished with A[i-1].
* - Therefore, we enforce a strict relative ordering: Identical elements must be used
* in their original sorted order (1a then 1b, never 1b before 1a).
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= |A| <= 9
*
* Time Complexity:
* O(N * N!)
* - There are N! permutations in the worst case (all unique).
* - Copying to result takes O(N).
* - N=9 -> 362,880 permutations. Efficient enough.
*
* Space Complexity:
* O(N) - Recursion stack and visited array.
*
* ---------------------
* 4. Input / Output Format
* ---------------------
* Input:
* - Integer Array A.
*
* Output:
* - 2D Array (ArrayList of ArrayLists) of unique permutations.
*
* ---------------------
* 5. Examples
* ---------------------
* Input: A = [1, 1, 2]
* Sort: [1a, 1b, 2]
*
* 1. Pick 1a: Remainder [1b, 2] -> Permutations [1a, 1b, 2], [1a, 2, 1b]
* 2. Pick 1b: SKIP (Because 1a is unused/unvisited).
* 3. Pick 2: Remainder [1a, 1b] -> Permutation [2, 1a, 1b]
* (Note: Inside this branch, 1b is skipped until 1a is picked).
*
* Output:
* [ [1, 1, 2],
* [1, 2, 1],
* [2, 1, 1] ]
*
* ============================================================================================
*/
public class AllUniquePermutations {
public int solve(int A) {
// TODO: Implement solution
return 0;
}
public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> input1) {
return new ArrayList<>();
}
}