Permutations

Medium

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

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]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

Here is a backtrack function which takes a currentList which have the current combination and a resultList which contains the all possible permutations.

  • If the currentList size is equal to the input array length then we are done with one such permutation.
  • Iterate over the integers from 0th index to index n - 1.
    • Place i-th integer in the permutation, and mark this as used.
    • Proceed to create all permutations and add digits in the permutation which are not used in the previous call.
    • Now backtrack, i.e. mark the previously used digits as unused and remove the same from the currentList.
class Solution {
    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        List<Integer> current = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        generatePermutations(nums, current, used, result, nums.length);
        return result;
    }

    private void generatePermutations(int[] nums, List<Integer> current,
                                      boolean[] used, List<List<Integer>> result, int n) {
        if (n == current.size()) {
            result.add(new ArrayList<>(current));
        } else {
            for (int i = 0; i < n; i++) {
                int cur = nums[i];
                if (used[i]) continue;
                current.add(cur);
                used[i] = true;
                generatePermutations(nums, current, used, result, n);
                used[i] = false;
                current.remove(current.size() - 1);
            }
        }
    }
}

Categories: Backtracking

1 reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s