AC Java backtracking solution beats 91%


  • 0
    S
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums == null || nums.length == 0) return res;
            Arrays.sort(nums);
            boolean[] visited = new boolean[nums.length];
            backtrack(res, new ArrayList<>(), nums, visited); 
            return res;
        }
        
        private void backtrack(List<List<Integer>> res, List<Integer> current, int[] nums, boolean[] visited) {
            if (current.size() == nums.length) {
                res.add(new ArrayList<>(current));
                return;
            }
            int j = -1;
            for (int i = 0; i < nums.length; i++) {
                if (visited[i]) continue;
                if (j == -1 || nums[i] != nums[j]) {
                    current.add(nums[i]);
                    visited[i] = true;
                    backtrack(res, current, nums, visited);
                    visited[i] = false;
                    current.remove(current.size() - 1);
                    j = i;
                }
            }
        }
    }
    

Log in to reply
 

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