Java simple recursive backtracking using boolean mark[] w/ comments


  • 0
    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            if (nums == null || nums.length == 0)
                return list;
            permuteHelper(list, new ArrayList<>(), nums, new boolean[nums.length]);
            return list;
        }
        private void permuteHelper(List<List<Integer>> list, List<Integer> perm, int[] nums, boolean[] mark) {
            if (perm.size() == nums.length) {
                list.add(new ArrayList<>(perm));// add a copy of perm!
                return;
            }
    	// from all unused indices, choose 1 at a time and add to perm
            for (int i = 0; i < mark.length; i++) {
                if (!mark[i]) {
                    perm.add(nums[i]);
                    mark[i] = true; // mark index i as used.
                    permuteHelper(list, perm, nums, mark);
                    perm.remove(perm.size() - 1);
                    mark[i] = false; // mark i back to unused.
                }
            }
        }
    }

  • 0
    N

    what's the complexity of this algorithm, O(n^n)?


  • 0

    runtime is O(n! * n). there are n! permutations. each one has length n.


Log in to reply
 

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