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;
            }
        }
    }
}

Leave a Comment