AC solution in Java


  • 0
    L
    public class Solution {
        public List<List<Integer>> permute(int[] num) {
            List<List<Integer>> ans = new ArrayList<>();
            //permute(num, new BitSet(num.length), new ArrayDeque<>(), ans);
            List<Integer> permutation = new ArrayList<>();
            for (int n : num) permutation.add(n);
            permute2(permutation, 0, ans);
            return ans;
        }
        
        private void permute(int[] num, BitSet visited, Deque<Integer> permutation, List<List<Integer>> ans) {
            if (permutation.size() == num.length) {
                ans.add(new ArrayList<>(permutation));
            } else {
                for (int i = 0; i < num.length; i++) {
                    if (visited.get(i) == false) {
                        permutation.push(num[i]);
                        visited.set(i);
                        permute(num, visited, permutation, ans);
                        visited.clear(i);
                        permutation.pop();
                    }
                }
            }
        }
        
        
        // This method does not need an extra bigset
        private void permute2(List<Integer> permutation, int begin, List<List<Integer>> ans) {
            if (begin >= permutation.size()) {
                ans.add(new ArrayList<>(permutation));
            } else {
                for (int i = begin; i < permutation.size(); i++) {
                    Collections.swap(permutation, begin, i);
                    permute2(permutation, begin + 1, ans);
                    Collections.swap(permutation, begin, i);
                }
            }
        }
    }

  • 0
    F

    One question.
    permute2(permutation, begin + 1, ans);
    why you use begin+1 instead of i+1??


Log in to reply
 

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