Shortest and simple Java recursive solution. Beating 77%


  • 1

    The idea to resolve duplicate is to ensure that for elements with the same value, we make sure that they maintain the ascending order of index in permutations. To implement this, each time we insert the ith number, we only insert its after the last element with the same value, to keep the order.

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            search(0, nums, new ArrayList<Integer>(), res);
            
            return res;
        }
        
        private void search(int i, int[] nums, List<Integer> list, List<List<Integer>> res) {
            if (i == nums.length) {
                res.add(new ArrayList<>(list));
                return;
            }
    	for (int k = list.size(); k >= 0; k--) {
                if (k < list.size() && list.get(k) == nums[i]) break;
                list.add(k, nums[i]);
                search(i + 1, nums, list, res);
                list.remove(k);
            }
        }
    }
    

Log in to reply
 

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