A fast and easy to understand Java solution


  • 0
    Z

    Basically my solution is to using HashSet to backtrack the indexes, Stack to store the temporary result and a recursive helper function to obtain all the possible permutations.

    public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        Stack<Integer> curr = new Stack<>();
        HashSet<Integer> hashNums = new HashSet<Integer>();
        helper(nums, nums.length, curr, hashNums, results);
        return results;
    }
    private void helper(int[] nums, int n, Stack<Integer> curr, HashSet<Integer> hashNums
                        , List<List<Integer>> results){
        if(n==0)
            results.add(new ArrayList(curr));
        else{
            for(int i=0;i<nums.length; i++){
                if(!hashNums.contains(i)){
                    hashNums.add(i);
                    curr.push(nums[i]);
                    helper(nums, n-1, curr, hashNums, results);
                    curr.pop();
                    hashNums.remove(i);
                }
            }
        }
    }
    

    }


  • 0
    M

    why we need to add a new ArrayList(cur) to result, not just result.add(current);?
    I mean in the helper function, results.add(new ArrayList(curr))
    not just results.add(curr);


  • 0
    Z

    http://stackoverflow.com/questions/15292980/java-arraylist-pass-by-reference
    Passing arraylist is passing references. We need to generate new copy of curr.


  • 0
    M

    Thank you so much! That will be very helpful!


Log in to reply
 

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