2014年5月11日星期日

Loop Solution - Permutation II

The idea is to swap the array passed in, and load the result when one completed swap is done.

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        perm(results, num, 0, num.length - 1);
        return results;
    }
   
    private void perm(ArrayList<ArrayList<Integer>> results, int[] num, int k, int n){
        if(k == n){
            ArrayList<Integer> result = new ArrayList<Integer>();
            for(int i = 0; i < num.length; i++){
                result.add(num[i]);
            }
            results.add(result);
        }else{
            for(int i = k; i <= n; i++){
                if(isSwap(num, k, i)){
                    continue;
                }
                int temp = num[i];
                num[i] = num[k];
                num[k] = temp;
               
                perm(results, num, k + 1, n);
               
                temp = num[i];
                num[i] = num[k];
                num[k] = temp;
            }
        }
    }
   
    private boolean isSwap(int[] num, int k, int i){
        for(int j = k; j < i; j++){
            if(num[j] == num[i]){
                return true;
            }
        }
        return false;
    }

}

没有评论: