Accepted Dynamic Programming Solution in Java(With Explanation)


  • 0
    F
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> cur = new ArrayList<List<Integer>>();
        List<List<Integer>> prev = new ArrayList<List<Integer>>();
        prev.add(new ArrayList<Integer>(Arrays.asList(nums[0])));
        for (int i = 1; i < nums.length; i++){
            for (List<Integer> list: prev){
                for (int j = 0; j <= list.size(); j++){
                    list.add(j, nums[i]);
                    cur.add(new ArrayList<Integer>(list));
                    list.remove(j);
                }
            }
            prev = cur;
            cur = new ArrayList<List<Integer>>(); 
        }
        return prev;
    }
    

    The idea is that the permutation of case (i) can be achieved by inserting nums[i] into all possible spots of all permutation of case(i - 1).
    For example, [1, 2] has two permutations [1, 2] and [2, 1].
    The permutation of [1, 2, 3] can be achieved by inserting 3 into every possible spot of [1, 2] and [2, 1]. Then for [1, 2], we can have [3,1, 2], [1, 3, 2], and [1, 2, 3]. For [2, 1], we can have [3, 2, 1], [2, 3, 1], and [2, 1, 3].


Log in to reply
 

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