Leetcode 47: Permutations II

1. Problem Statement (Simple Explanation):

You’re given an array nums that may contain duplicates.

You must return all unique permutations of nums.
The order of permutations in the output does not matter.

2. Examples:

Example 1:

Input: nums = [1,1,2]

All permutations (with duplicates):

[1,1,2]
[1,2,1]
[1,1,2] (duplicate)
[1,2,1] (duplicate)
[2,1,1]
[2,1,1] (duplicate)

Unique permutations:

[

[1,1,2],

[1,2,1],

[2,1,1]

]

Example 2:

Input: nums = [1,2,3]

All permutations are unique:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

3. Approach – Backtracking with Duplicate Handling:

This is similar to Problem 46 (Permutations) but nums may contain duplicates, so naive permutation will produce duplicate lists. We need to avoid generating duplicates instead of removing them afterwards.

Standard trick: sort + skip equal values at same depth:

Steps:

Sort the array nums.
Then duplicates are adjacent.
Use backtracking with:

current – current permutation being built.
used[i] – whether nums[i] is already in current at this point.

At each depth, when iterating indices i from 0 to n-1:

Skip if used[i] is already true (value already in permutation).
To avoid duplicates:

If i > 0 and nums[i] == nums[i-1] and used[i-1] == false,
skip i.

Why?

For duplicates (e.g., nums = [1a, 1b, 2] after sorting [1,1,2]):

At a given depth, we only allow the first unused duplicate to be chosen.
If nums[i] == nums[i-1] and we did not use the previous one at this level, using nums[i] instead would produce permutations we already generated with nums[i-1].

When current size equals nums.length, we have a full permutation; add a copy to the result.

Pseudo-code:

Complexity:

Let n = len(nums) (≤ 8):

In worst case (distinct numbers), we have n! permutations.
Time: O(n·n!) (building each permutation).
Space: O(n) extra for use and recursion (excluding output).

For n <= 8, 8! = 40320 → absolutely fine.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code:

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog