Short java AC solution using iterative DFS

  • 1
    import java.util.AbstractMap.SimpleEntry;
    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            List<Integer> list1 = new ArrayList<>();
            Stack<Map.Entry<Integer,Integer>> st = new Stack<>();
            st.push(new SimpleEntry<>(-1,-1));//key is the index in list1 that will be added on
                Map.Entry<Integer,Integer> entry = st.pop();
                while(entry.getKey()>=0&&list1.size()>entry.getKey())    list1.remove(list1.size()-1);//backtracking
                if(entry.getKey()>-1) list1.add(entry.getValue());
                    list.add(new ArrayList<>(list1));
                for(int i: nums)    if(!list1.contains(i))   st.push(new SimpleEntry<>(list1.size(),i));
            return list;

    Used a AbstractMap.SimpleEntry to hold both index and value into dfs stack, where index is used to backtracking. The runtime is a little higher than simply using recursive swapping backtracking, but both are O(n!);

Log in to reply

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