Backtracking Part 3 — Permutations Problems

QUESTION 1 — Permutations

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

THOUGHT PROCESS FOR BACKTRACKING SOLUTION — 1

The Backtracking Brahmastra :

Typical decision tree (pardon for the poor handwriting)
class Solution {
public:
vector<vector<int>> ans;

void helper(vector<int>& nums, vector<int>& currans){
if(currans.size() == nums.size()){
ans.push_back(currans);
return;
}

for(int i = 0; i < nums.size(); i++){
//if the currans is already having nums[i], we skip this call(won't //work in case of duplicates)
if(find(currans.begin(),currans.end(),nums[i]) != currans.end()) continue;
currans.push_back(nums[i]);
helper(nums,currans);
currans.pop_back();
}

}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> currans = {};
helper(nums,currans);
return ans;
}

};

THOUGHT PROCESS FOR BACKTRACKING SOLUTION — 2

#include <bits/stdc++.h>
using namespace std;
void permute(string s, int i, int n){
if(i == n){
cout << s << " ";
return;
}
for(int j = i; j < n; j++){
swap(s[j],s[i]);
permute(s,i+1,n);
swap(s[j],s[i]);
}
}
int main()
{
string s;
cin >> s;
permute(s,0,s.size()-1);
}

QUESTION 2 — Permutations II

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
class Solution
{
public:
vector<vector<int>> ans;
void helper(vector<int> &nums, vector<int> &currans, vector<int> &used)
{
if (currans.size() == nums.size())
{
ans.push_back(currans);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if(used[i] == 1 || i > 0 && nums[i]==nums[i - 1] && used[i-1]==1)
continue;
used[i] = 1;
currans.push_back(nums[i]);
helper(nums, currans, used);
used[i] = 0;
currans.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int> &nums)
{
vector<int> currans = {};
vector<int> used(nums.size(), 0);
sort(nums.begin(), nums.end());
helper(nums, currans, used);
return ans;
}
};

THANK YOU FOR READING. All your suggestions are welcomed to improve more. Encourage me to write more by appreciating if you like the article.

SEE YOU IN THE NEXT PART WITH QUESTIONS RELATED TO COMBINATIONS :)

--

--

Software Developer working to become a better Software Developer everyday :)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Manvi Tyagi

Software Developer working to become a better Software Developer everyday :)