Day 13 : All Possible Permutations - String

In below code we will be using simple recursion to create all possible permutations.

• we will be creating an inp array, for convienience as we wil be removing elements from this array each time we append to the result, so that the next permtn will exclude already used elements.
• Stringbuilder is used to append each char.

Algo;

    if input array is empty, i.e no more elements need to be added, store the string in result.

else travel through the input array, append the char to stringBuilder, remove it from input arrayList

and call append method again.

After returning, revert back the changes.

Kl refer below code

import java.util.* ;

import java.io.*; 

public class Solution {

    public static List<String> findPermutations(String s) {

        List<String> res = new ArrayList<>();

        List<Character> inp = new ArrayList<>(s.length());

        for(int i=0; i<s.length(); i++)

            inp.add(s.charAt(i));

        StringBuilder b = new StringBuilder();

        append(b, inp, res);

        return res;

    }




    public static void append(StringBuilder b, List<Character> inp, List<String> res){

        if(inp.size() == 0){

            res.add(b.toString());

            return;

        }

        for(int i=0; i<inp.size(); i++){

            char c = inp.get(i);

            b.append(c);

            inp.remove(i);

            append(b, inp, res);

            inp.add(i, c);

            b.deleteCharAt(b.length()-1);

        }

    }

}

Happy coding  ; ~)

#include <bits/stdc++.h> 

using namespace std;

void TP(string &s, vector<string> &ans,map<int,bool> &mp,string &temp){

    if(s.size()==temp.size()){

        ans.push_back(temp);

        return;

    }

    for(int i=0;i<s.size();i++){

        if(mp[i]){

            temp.push_back(s[i]);

            mp[i]=false;

            TP(s,ans,mp,temp);

            mp[i]=true;

            temp.pop_back();

        }

    }

}

vector<string> findPermutations(string &s) {

    vector<string> ans;

    int n=s.size();

    string temp;

    map<int,bool> mp;

    for(int i=0;i<s.size();i++) mp[i]=true;

    TP(s,ans,mp,temp);

    return ans;

}

import java.util.* ;

import java.io.*; 

public class Solution {

    static void swap(char[]s,int i,int j)

    {

        char temp = s[i];s[i]=s[j];s[j]=temp;

    }

    static void solve(char[] s,List<String>ans,int pointer)

    {

        if(pointer==s.length)

        {

            ans.add(new String(s));

            return;

        }

        for(int i=pointer; i<s.length; ++i)

        {

            swap(s,i,pointer);

            solve(s, ans, pointer+1);

            swap(s,i,pointer);

        }

    }

    public static List<String> findPermutations(String s) {

        // Write your code here.

        List<String>ans=new ArrayList<>();

        solve(s.toCharArray(),ans,0);

        return ans;

    }

}

#include <bits/stdc++.h>


void solve(string &s, string &perm, vector<string> &ans, int idx){
    //base case
    if(idx==s.size()){
        ans.push_back(perm);
        return;
    }


    for(int i=0; i<=perm.size(); i++){
        perm.insert(i, 1, s[idx]);
        solve(s, perm, ans, idx+1);
        perm.erase(i, 1);
    }
    


}
vector<string> findPermutations(string &s) {
    string perm;
    vector<string> ans;
    perm.push_back(s[0]);
    solve(s, perm, ans, 1);


    return ans;
}

#include <bits/stdc++.h> 

void solve(string &s, int i, vector<string>& str){

    if(i >= s.length()){

        str.push_back(s);

        return;

    }

    for(int k = i; k < s.length(); k++){

        swap(s[i], s[k]);

        solve(s, i+1, str);

        swap(s[i], s[k]);

    }

}

vector<string> findPermutations(string &s) {

    vector<string> str;

    solve(s,0, str);

    return str;

}

import java.util.* ;

import java.io.*; 

public class Solution {

    public static List<String> findPermutations(String s) {

        // Write your code here.

         List<String> result = new ArrayList<>();

         helper(result, s, 0, "", new boolean[s.length()]);

         return result;

    }

    private static void helper( List<String> result, String s, int index,String temp,boolean vis[]){

        if (index==s.length()) {

             result.add(temp);

             return;

        }

        for (int i = 0; i < s.length(); i++) {

            if (vis[i]) {

                continue;

            }

            vis[i] = true;

            helper(result, s, index+1, temp+String.valueOf(s.charAt(i)), vis);

             vis[i] = false;

        }

    }

}

#include <bits/stdc++.h>

//function to solve the question recursively
void solve (int idx, string s, vector<string>& ans) {

    //base case
    if (idx >= s.size()) {
        ans.push_back(s);
        return;
    }

    string temp = s;

    for (int i = idx; i < s.size(); i++) {
        swap(s[idx], s[i]);
        solve(idx+1, s, ans);
        s = temp;
    }

    return;
}

vector<string> findPermutations(string &s) {

    vector<string> ans;
    solve(0, s, ans);

    return ans;
}

from os import *
from sys import *
from collections import *
from math import *


def helper(s, i, n, prev, ans):
	if i == n:
		ans.append("".join(prev))
		return
	for j in range(n):
		if prev[j] == '0':
			prev[j] = s[i]
			helper(s, i+1, n, prev, ans)
			prev[j] = '0'

def findPermutations(s):
	ans = []
	n = len(s)
	prev = ['0']*n
	helper(s, 0, n, prev, ans)
	return ans

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void getpermute(string a, int i, vector<string> &str)

{

    if (i == a.length() - 1)

    {

        str.push_back(a);

        return;

    }

    for (int j = i; j < a.length(); j++)

    {

        swap(a[i], a[j]);

        getpermute(a, i + 1, str);

        swap(a[i], a[j]);

    }

}

int main(void)

{

    string a;

    cin >> a;

    vector<string> str;

    int length = a.length();

    getpermute(a, 0, str);

    for (const auto &a : str)

    {

        cout << a << " ";

    }

}

def findPermutations(s):

    string = list(s)

    n = len(string)

    res = []

    def backtrack(start):

        if start == n:

            res.append("".join(string))

            return

        for i in range(start, n):

            string[start], string[i] = string[i], string[start]  # Swap elements

            backtrack(start + 1)

            string[start], string[i] = string[i], string[start]  # Backtrack, restore original order

    backtrack(0)

    return res