Java Backtracking Solution


  • 6
    L
    public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return lists;
        }
    
        dfs(nums, lists, new ArrayList<Integer>());
        return lists;
    }
    
    private void dfs(int[] nums, List<List<Integer>> lists, List<Integer> cur) {
        if (cur.size() == nums.length) {
            List<Integer> list = new ArrayList<>(cur);
            lists.add(list);
        }
    
        for (int i = 0; i < nums.length; i++) {
            if (cur.contains(nums[i])) {
                continue;
            }
            cur.add(nums[i]);
            dfs(nums, lists, cur);
            cur.remove(cur.size() - 1);
        }
    }
    

    }


  • 0

    the contains() takes O(n) time which wastes time.


  • 0
    L

    yea I think we can resolve it by adding a hashset.


  • 0
    Y
    This post is deleted!

  • 0
    M

    Improving a little using hashset as you commented based on your solution:

    public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums==null||nums.length==0) return res;
        List<Integer> curtPermu = new ArrayList<Integer>();
        HashSet<Integer> set = new HashSet<Integer>();
        dfs(res,curtPermu,nums,set);
        return res;
    }
    private void dfs(List<List<Integer>> res, List<Integer> curtPermu, int[] nums, HashSet<Integer> set){
        if(curtPermu.size()==nums.length){
            res.add(new ArrayList<Integer>(curtPermu));
            return;
        }
        for(int i=0; i<nums.length; i++){
            if(set.contains(nums[i])) continue;
            curtPermu.add(nums[i]);
            set.add(nums[i]);
            dfs(res, curtPermu, nums, set);
            set.remove(curtPermu.get(curtPermu.size()-1));
            curtPermu.remove(curtPermu.size()-1);
        }
    }
    

    }


  • 0
    L

    yes you are right.
    A little bit change might make code cleaner:
    you can just write:

    set.remove(nums[i]);


Log in to reply
 

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