Two BackTracking Solutions. Which one is better?


  • 0
    R

    First. Insert new item to different position:

    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            res.add(list);
            for (int i = 0; i < nums.length; i++) {
                List<List<Integer>> cur = new ArrayList<>();
                for (List<Integer> l : res) {
                    int size = l.size();
                    for (int j = 0; j <= size; j++) {
                        l.add(j, nums[i]);
                        cur.add(new ArrayList<>(l));
                        l.remove(j);
                    }
                }
                res = cur;
            }
            return res;
        }
    }
    

    Second, use a flag table:

    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            boolean[] visited = new boolean[nums.length];
            search(res, list, visited, nums);
            return res;
        }
        
        private void search(List<List<Integer>> res, List<Integer> list, boolean[] visited, int[] nums) {
            if (list.size() == nums.length) {
                res.add(new ArrayList<>(list));
                return;
            }
            for (int i = 0; i < visited.length; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    list.add(nums[i]);
                    search(res, list, visited, nums);
                    visited[i] = false;
                    list.remove(list.size() - 1); 
                } 
            }
        }
    }
    

    I think the time complexity for both methods should be O(n!).
    The second one seems more space efficient to me. Let me know if I'm wrong.
    Thanks!


Log in to reply
 

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