# Recursion – Permutations

## Permutation of String

``````public class Main
{
public static void main(String[] args) {
permutation("", "abc");
}

public static void permutation(String p, String up) {
if(up.isEmpty()) {
System.out.println(p);
return;
}

char ch = up.charAt(0);

for(int i=0; i<=p.length(); i++) {
String f = p.substring(0, i);
String s = p.substring(i, p.length());
permutation(f+ch+s, up.substring(1));
}
}
}
``````
``````import java.util.*;
public class Main
{
public static void main(String[] args) {
System.out.println(permutation("", "abc"));
}

public static ArrayList<String> permutation(String p, String up) {
if(up.isEmpty()) {
ArrayList<String> list = new ArrayList<>();
list.add(p);
return list;
}

char ch = up.charAt(0);

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

for(int i=0; i<=p.length(); i++) {
String f = p.substring(0, i);
String s = p.substring(i, p.length());
ans.addAll(permutation(f+ch+s, up.substring(1)));
}

return ans;
}
}
``````

## Permutation of Array

``````class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> curr = new ArrayList<>();
boolean[] freq = new boolean[nums.length];
helper(nums, curr, ans, freq);
return ans;
}

public static void helper(int[] nums, List<Integer> curr, List<List<Integer>> ans, boolean[] freq) {
if(curr.size()==nums.length) {
ans.add(new ArrayList<>(curr));
return;
}

for(int i=0; i<nums.length; i++) {
if(freq[i]==false) {
freq[i]=true;
curr.add(nums[i]);
helper(nums, curr, ans, freq);
curr.remove(curr.size()-1);
freq[i]=false;
}
}
}
}``````
Categories DSA