Simple Java solution without swap


  • 4
    X
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if (nums == null || nums.length == 0)
            return result;
        helper(new ArrayList<Integer>(), result, nums);
        return result;
    }
    
    private void helper(List<Integer> current, List<List<Integer>> result, int[] nums) {
        if (current.size() == nums.length) {
            result.add(new ArrayList(current));
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (!current.contains(nums[i])) {
                current.add(nums[i]);
                helper(current, result, nums);
                current.remove(current.size() - 1);
            }
        }
    }

  • 2
    M

    why we need to add a new ArrayList(current) to result, not just result.add(current);?


  • 0
    7

    there's only one "current" list and it's recording each backtracking step so it's always being changed


  • 0
    X

    My answer is the same as yours, but I think it cost too much time."!current.contains(nums[i])" this sentence may cost a lot, do you have any other idea better than use "!current.contains(nums[i])"?????


Log in to reply
 

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