Simple Java Recursive Solution


  • 0

    This recursive solution may not be fast, but very easy to understand, and can handle the case of Permutation II, just uncomment some code.

    public class Solution {
        
        public List<List<Integer>> permuteAux(ArrayList<Integer> nums) {
            List<List<Integer>> l = new ArrayList<List<Integer>>();
            if(nums.size() == 0) {
                l.add(new ArrayList<Integer>());
                return l;
            }
            for(int i=nums.size()-1; i>=0; i--) {
                //if(i==0 || nums.get(i-1) != nums.get(i)) { // un-comment this to get rid of duplicate sequences!
                    ArrayList<Integer> subL = new ArrayList<Integer>();
                    subL.add(nums.get(i));
                    ArrayList<Integer> nums2 = (ArrayList<Integer>)nums.clone();
                    nums2.remove(i);
                    List<List<Integer>> tails = permuteAux(nums2);
                    for(List<Integer> subTail : tails) {
                        ArrayList<Integer> subLClone = (ArrayList<Integer>)subL.clone();
                        subLClone.addAll(subTail);
                        l.add(subLClone);
                    }
               }
            //}
            return l;
        }
        
        public List<List<Integer>> permute(int[] nums) {
            Arrays.sort(nums);
            ArrayList<Integer> numsArr = new ArrayList<Integer>();
            for(int n : nums)
                numsArr.add(n);
            return permuteAux(numsArr);
        }
    }

Log in to reply
 

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