Three Solutions in Java (Both recursive and iterative)


  • 0
    M

    Solution 1: Backtracking, Recursive. Store index instead of value in path to avoid picking the used candidate.

    public class Solution {
        List<List<Integer>> permute(int[] a) {
            List<List<Integer>> result = new ArrayList<>();
            if (a == null || a.length == 0) return result;
            Arrays.sort(a);
            backtrack(a, result, new ArrayList<>());
            return result;
        }
    
        void backtrack(int[] a, List<List<Integer>> result, List<Integer> path) {
            if (path.size() == a.length) {
                List<Integer> real = new ArrayList<>();
                for (int idx : path) real.add(a[idx]);
                result.add(real);
                return;
            }
    
            for (int i = 0; i < a.length; i++) {
                if (!path.contains(i)) {
                    path.add(i);
                    backtrack(a, result, path);
                    path.remove(path.size() - 1);
                    while (i + 1 < a.length && a[i + 1] == a[i]) i++;
                }
            }
        }
    }
    

    Solution 2: DP (DFS), iterative. Using two result to backup each other.

    public class Solution {
        List<List<Integer>> permute3(int[] a) {
            List<List<Integer>> result = new ArrayList<>();
            if (a == null || a.length == 0) return result;
            result.add(new ArrayList<>());
            for (int round : a) {                                      
                List<List<Integer>> temp = new ArrayList<>();
                for (List<Integer> path : result) {                   
                    for (int pos = 0; pos <= path.size(); pos++) {
                        if (pos > 0 && path.get(pos - 1) == round) break; 
                        List<Integer> newpath = new ArrayList<>(path);
                        newpath.add(pos, round);
                        temp.add(newpath);
                    }
                }
                result = temp;
            }
            return result;
        }
    }
    

    Solution 3: DP (DFS), iterative. Using queue to update result set in each round.

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] a) {
            LinkedList<List<Integer>> result = new LinkedList<>();
            if (a == null || a.length == 0) return result;
            result.add(new ArrayList<>());
            for (int round : a) {                                     
                int size = result.size();
                for (int i = 0; i < size; i++) {                  
                    List<Integer> path = result.remove();
                    for (int pos = 0; pos <= path.size(); pos++) {      
                        if (pos > 0 && path.get(pos - 1) == round) break;  
                        List<Integer> newpath = new ArrayList<>(path);
                        newpath.add(pos, round);
                        result.add(newpath);
                    }
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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