Leetcode 46: Permutations

1. Problem Statement (Simple Explanation):

You’re given an array nums of distinct integers.

You must return all possible permutations of nums (all possible orderings).
The answer can be returned in any order.

2. Examples:

Example 1:

Input: nums = [1,2,3]

Output:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

Example 2:

Input: nums = [0,1]

Output:

[

[0,1],

[1,0]

]

Example 3:

Input: nums = [1]

Output:

[

[1]

]

3. Approach – Backtracking (DFS):

This is a classic permutations problem.

Intuition:

We build permutations one position at a time:

At each step, we choose one of the remaining unused numbers to place next.
We continue until we have used all numbers → one complete permutation.
Then we backtrack and try another choice.

Since all integers in nums are distinct, we don’t need special duplicate handling.

Two common implementations:

Using a used[] boolean array and a current list.
Doing in-place swapping in nums.

Here I’ll use the used[] + current variant (very clear), and you can mention swap-variant as a note.

Algorithm:

Have:

result – list of all permutations.
current – current permutation being built.
used[i] – whether nums[i] is already in current.

Define backtrack():

If len(current) == len(nums):

Add a copy of current to result.
Return.

Else:

For each index i from 0 to n-1:

If used[i] is false:

Mark used[i] = true.
Append nums[i] to current.
Recurse: backtrack().
Backtrack:

Pop last from current.
Set used[i] = false.

Call backtrack() initially with empty current.

Pseudo-code:

Complexity:

Let n = len(nums):

There are n! permutations.
Each permutation of length n is built step-by-step:

Time: O(n*n!) (n permutations, each copy of length n)

Space:

O(n) recursion depth + O(n) for used and current
O(n) auxiliary (excluding output)

n ≤ 6 → 6! = 720 permutations → very manageable.

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