Recursive Java Solution


  • 0
    S

    Here I share my java solution using recursion for permutation.


  • 19
    S
    public class Solution {
        boolean [] isUsed;
        int numLength;
        ArrayList<ArrayList<Integer>> output;
        ArrayList <Integer> al;
        
        public ArrayList<ArrayList<Integer>> permute(int[] num) {
            numLength = num.length;
            al = new ArrayList <Integer>();
            output = new ArrayList<ArrayList<Integer>>();
            isUsed = new boolean[num.length];
            doPermutation(0, num);
            return output;
        }
        public void doPermutation(int index, int[] num) {
            // base case
            if (index == numLength) {
                output.add((ArrayList<Integer>)al.clone());
                return;
            }
            for (int i = 0; i < numLength; i++) {
                if (!isUsed[i]) {
                    al.add(num[i]);
                    isUsed[i] = true;
                    doPermutation(index + 1, num);
                    isUsed[i] = false;
                    al.remove(index);
                }
            }
        }
    }

  • 0
    S

    Hi @sean thanks for your sharing. It would be better to word thoughts, not only paste code here. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    A

    Nice! I like this way!


  • 0
    E

    That's pretty neat.
    But
    "output.add((ArrayList<Integer>)al.clone());"
    this phrase can't work on my computer. I can only instead use
    "List<Integer> bl = new ArrayList<Integer> (al);
    output.add(bl);"
    could you please tell me the reason?


  • 0
    S

    I am not really sure why the clone() is not working. But certainly you can do following:
    --> output.add(new ArrayList<Integer>(al));

    The result should be the same.


  • 0
    P

    Great solution. Similar to mine. Is this O(|n|)? The first time the function will enter the loop n times. In each of those n times it calls the function again and the new ones will enter the loop n-1 times (nn-1 so far). It will end up as: (nn-1n-2...*(n-(n-1)) = O(|n|)?

    Another question: Isn't that a DFS solution?


  • 0
    W

    Also share mine, recursion without global variable map, pretty straight forward:

    public List<List<Integer>> permute(int[] num) {
            int n = num.length;
            if(num == null || num.length == 0)
                return null;
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            List<Integer> ini = new ArrayList<Integer>();
            ini.add(num[0]);
            res.add(ini);
            if(num.length == 1)
            {
            	return res;
            }
            else
            	res.clear();
            int[] preArr = new int[n-1];
            for(int i = 0; i< n-1; i++)
            {
            	preArr[i] = num[i];
            }
            
            List<List<Integer>> pre = permute(preArr);
            int last = num[n-1];
            for(List<Integer> list : pre){
            	res.addAll(insert(last, list));
            }
            
            return res;
        }
        
        public List<List<Integer>> insert(int n,  List<Integer> list)
        {
        	List<List<Integer>> res = new ArrayList<List<Integer>>();
        	for(int i = 0; i<=list.size(); i++)
        	{
        		List<Integer> temp = new ArrayList<Integer>();
        		temp.addAll(list);
        		temp.add(i, n);
        		res.add(temp);
        	}
        	return res;
        }

  • 2
    W

    My method is to change the every position of the element to the first place, and permute the rest. except the first one. If you want make the order of output is lexicographical, just remove the comment tag.

    public class Solution {
        
        private List<List<Integer>> res;
        
        private void permuteHelper(int num[], int idx) {
            if (idx == num.length) {
                res.add(getOne(num));
                return;
            }
            for (int j=idx;j<num.length;j++) {
                //Arrays.sort(num, idx, num.length);
                swap(num,idx,j);
                permuteHelper(num,idx+1);
                swap(num,idx,j);
            }
        }
        
        private void swap(int num[], int i, int j) {
            int tmp = num[i];
            num[i] = num[j];
            num[j] = tmp;
        }
        
        private List<Integer> getOne(int num[]) {
            List<Integer> tmp = new ArrayList<Integer>();
            for (int i=0;i<num.length;i++) tmp.add(num[i]);
            return tmp;
        }
        
        public List<List<Integer>> permute(int[] num) {
            res = new ArrayList<List<Integer>>();
            permuteHelper(num, 0);
            return res;
        }
    
    }
    

    It is also can write in another way like the code below.

    public class Solution {
        
        private List<List<Integer>> res;
        
        private void permuteHelper(int num[], int idx) {
            res.add(getOne(num));
            for (int i=idx;i<num.length-1;i++) {
                for (int j=i+1;j<num.length;j++) {
                    swap(num,i,j);
                    permuteHelper(num,i+1);
                    swap(num,j,i);
                }
            }
        }
        
        private void swap(int num[], int i, int j) {
            int tmp = num[i];
            num[i] = num[j];
            num[j] = tmp;
        }
        
        private List<Integer> getOne(int num[]) {
            List<Integer> tmp = new ArrayList<Integer>();
            for (int i=0;i<num.length;i++) tmp.add(num[i]);
            return tmp;
        }
        
        public List<List<Integer>> permute(int[] num) {
            res = new ArrayList<List<Integer>>();
            permuteHelper(num, 0);
            return res;
        }
    }

  • 0
    J

    I have exactly the same thing except the part where you clone the arraylist. Didn't really understand why until I see this. Thanks for the solution!


  • 0
    G
    This post is deleted!

  • 0
    G

    I actually found a good video explanation:
    https://www.youtube.com/watch?v=0TgbziCDGgw


  • 2
    G

    I think it's hard to understand the best answer so I ran and printed out part of the execution on input [1,2,3,4]. Hope this helps other people

    i=0	 isUsed:[0, 0, 0, 0]	[1]
    i=1	 isUsed:[1, 0, 0, 0]	[1, 2]
    i=2	 isUsed:[1, 1, 0, 0]	[1, 2, 3]
    i=3	 isUsed:[1, 1, 1, 0]	[1, 2, 3, 4]
    added:	[1, 2, 3, 4]
    i=3	 isUsed:[1, 1, 1, 0]	[1, 2, 3]
    i=2	 isUsed:[1, 1, 0, 0]	[1, 2]
    i=3	 isUsed:[1, 1, 0, 0]	[1, 2, 4]
    i=2	 isUsed:[1, 1, 0, 1]	[1, 2, 4, 3]
    added:	[1, 2, 4, 3]
    i=2	 isUsed:[1, 1, 0, 1]	[1, 2, 4]
    i=3	 isUsed:[1, 1, 0, 0]	[1, 2]
    i=1	 isUsed:[1, 0, 0, 0]	[1]
    i=2	 isUsed:[1, 0, 0, 0]	[1, 3]
    i=1	 isUsed:[1, 0, 1, 0]	[1, 3, 2]
    i=3	 isUsed:[1, 1, 1, 0]	[1, 3, 2, 4]
    added:	[1, 3, 2, 4]
    i=3	 isUsed:[1, 1, 1, 0]	[1, 3, 2]
    i=1	 isUsed:[1, 0, 1, 0]	[1, 3]
    i=3	 isUsed:[1, 0, 1, 0]	[1, 3, 4]
    i=1	 isUsed:[1, 0, 1, 1]	[1, 3, 4, 2]
    added:	[1, 3, 4, 2]
    i=1	 isUsed:[1, 0, 1, 1]	[1, 3, 4]
    i=3	 isUsed:[1, 0, 1, 0]	[1, 3]
    i=2	 isUsed:[1, 0, 0, 0]	[1]
    i=3	 isUsed:[1, 0, 0, 0]	[1, 4]
    i=1	 isUsed:[1, 0, 0, 1]	[1, 4, 2]
    i=2	 isUsed:[1, 1, 0, 1]	[1, 4, 2, 3]
    added:	[1, 4, 2, 3]
    i=2	 isUsed:[1, 1, 0, 1]	[1, 4, 2]
    i=1	 isUsed:[1, 0, 0, 1]	[1, 4]
    i=2	 isUsed:[1, 0, 0, 1]	[1, 4, 3]
    i=1	 isUsed:[1, 0, 1, 1]	[1, 4, 3, 2]
    added:	[1, 4, 3, 2]

  • 0
    L

    for case[1,1],will it return two [1,1]?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.