Skip to content

Instantly share code, notes, and snippets.

@anil477
Last active January 29, 2022 11:49
Show Gist options
  • Save anil477/0d4fc3a455a91143f22fd012063e38b6 to your computer and use it in GitHub Desktop.
Save anil477/0d4fc3a455a91143f22fd012063e38b6 to your computer and use it in GitHub Desktop.
47. Permutations II
public class Solution {
// https://leetcode.com/problems/permutations-ii/
// 47. Permutations II
// https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) return res;
boolean[] used = new boolean[nums.length];
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
dfs(nums, used, list, res);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
if(list.size()==nums.length){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
used[i]=true;
list.add(nums[i]);
dfs(nums,used,list,res);
used[i]=false;
list.remove(list.size()-1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment