Short java AC solution using iterative DFS


  • 1
    J
    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
            while(!st.isEmpty()){
                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());
                if(list1.size()==nums.length){
                    list.add(new ArrayList<>(list1));
                    continue;
                }
                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.