[leetcode]Permutations II

この問題を完成させるには、まずSubSet IIを振り返ってみましょう.  http://discuss.leetcode.com/questions/265/subsets-ii
1.subに入るたびに、現在のpathが結果(サブセット)であることが記録される.2.subに入ると、i個の要素のサブセットでi+1個の要素のサブセットを導く過程である.3.i個の要素があり、i+1個目の要素は元の集合Sの位置iの後の要素からのみ選択される.4.このアルゴリズムの鍵は、秩序正しく追加することです.生成された集合の要素が秩序化されていることを保証します.例えば[1,2,3,4,5](繰返しはしばらく考慮しない)subに入ったときが[1,3]であれば、次のステップは[1,3,4]と[1,3,5]がなぜ[1,3,2]なかったのか.5.秩序化のため、取得されたi個の要素の集合の最後の要素は、境界である.それを使って重さを判断することができます.
http://www.cnblogs.com/lautsie/p/3249869.html
しかし、Permutationにとって、本来は異なる順序を試してみることであり、秩序がないという概念は、どうすればいいのだろうか.
答えは、再帰するときに全く異なる方法を採用することです.(上のこの方法は、主に求子集に適用されるかもしれない.)しかし、肝心な判重部分では、重複する要素に対して秩序ある思想を採用している.
例えば、1 1 1 2と入力すると、最後に生成された組合せのうち2番目の1が1番目の1の後にあることを保証すれば、重複した組合せが発生しないことを保証することができる.1 1 1 2、1(1)1(2)2と表記され、それらが生成できるすべての組合せが1(2)を除いて1(1)より前の場合:1(1)1(2)21(1)2(2)2(1)1(2)1(2)を除いて求められる.
方法は:http://www.cnblogs.com/remlostime/archive/2012/11/13/2768816.html
まず配列を並べ替えて、DFSの場合、前の1つの数が自分と等しいかどうかを判断し、等しい場合は前の数を使わなければならないので、自分で使うことができ、重複した配列は発生しません.
最後に、最初に順番を決めることを忘れないでください.また、tmpをresultに追加する場合はnewを1部ください.そうしないと、後で空になります.

public class Solution {

    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();

    ArrayList<Integer> tmp = new ArrayList<Integer>();

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {

        ans.clear();

        tmp.clear();

        Arrays.sort(num);

        int len = num.length;

        boolean[] canUse = new boolean[len];

        for (int i = 0; i < len; i++)

        {

            canUse[i] = true;

        }

        sub(num, canUse);

        return ans;

    }

    

    private void sub(int[] num, boolean[] canUse)

    {

        if (tmp.size() == num.length)

        {

            ans.add(new ArrayList<Integer>(tmp));

        }

        else

        {

            for (int i = 0; i < num.length; i++)

            {

                if (canUse[i])

                {

                    if (i!=0 && num[i] == num[i-1] && canUse[i-1]) continue;

                    tmp.add(num[i]);

                    canUse[i] = false;

                    sub(num, canUse);

                    tmp.remove(tmp.size()-1);

                    canUse[i] = true;

                }

            }

        }

    }

}