Permutation

PROBLEM

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

Example1

*Input*: nums = [1,2,3]
*Output*: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example2

*Input*: nums = [0,1]
*Output*: [[0,1],[1,0]]

Example3

*Input*: nums = [1]
*Output*: [ [1] ]

Constraints

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

SOLVING

we’ll use Backtracking method

Steps

• Backtracking method:
  • push in result and return if current index equal size
  • for each index between current index and size:
    • swap in nums the element at current index and index from for loop
    • call in recursive the backtrack method with as parameter current index + 1
    • re swap in nums the element at current index and index from for loop to reset the change
• return result

Code

class Solution {
public:
  vector<vector<int>> permute(vector<int> &nums) {
    backtrack(nums, 0, nums.size());
    return result;
  }

private:
  vector<vector<int>> result;

  void backtrack(vector<int> &nums, int idx, int size) {
    if (idx == size)
      result.push_back(nums);
    else {
      for (int i = idx; i < size; i++) {
	swap(nums[idx], nums[i]);
	backtrack(nums, idx + 1, size);
	swap(nums[idx], nums[i]);
      }
    }
  }
};

• BACKTRACKING
• PROBLEM