Leetcode-Java/0046. Permutations at main · Hoaru/Leetcode-Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {

    // public void helper(ArrayList<Integer> num, ArrayList<Integer> cur, ArrayList<List<Integer>> res){
    //     if(num.size() == 0){
    //         res.add(cur);
    //         return;
    //     }
    //     else{
    //         for(int i = 0; i < num.size(); i++){
    //             ArrayList<Integer> newNum = new ArrayList<>(num);
    //             ArrayList<Integer> newCur = new ArrayList<>(cur);
    //             newNum.remove(num.get(i));
    //             newCur.add(num.get(i));
    //             helper(newNum, newCur, res);
    //         }
    //     }
    // }

    // public List<List<Integer>> permute(int[] nums) {
    //     ArrayList<List<Integer>> res = new ArrayList<>();
    //     ArrayList<Integer> newNum = new ArrayList<>();
    //     ArrayList<Integer> newCur = new ArrayList<>();
    //     for(int i : nums) newNum.add(i);
    //     helper(newNum, newCur, res);
    //     return res;
    // }

    public void helper(List<List<Integer>>res, List<Integer> curr, HashMap<Integer, Integer> map, int n) {
        if (curr.size() == n) {
            res.add(new ArrayList<>(curr));
        }
        else {
            for (int e : map.keySet()) {
                int val = map.get(e);
                if (val >= 1) {
                    curr.add(e);
                    map.put(e, val - 1);
                    helper(res, curr, map, n);
                    curr.remove(curr.size() - 1);
                    map.put(e, val);
                }
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res= new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int e: nums) {
            map.put(e, map.getOrDefault(e, 0) + 1);
        }
        helper(res, new ArrayList<>(), map, nums.length);
        return res;
    }
}