一、一个直接的思路是枚举每一种元素出现的次数，这里实际上是没有重复时的推广，没有重复的时候，出现次数是0 or 1.

返回条件：当前遍历的所有元素的个数已达到最大。

这里的关键实际上变为了如何枚举所有的个数，这种个数可以看做是一种状态，比如：

1 1 1 1 2 2 2 3 3 3 4 4

alldigits： 1 2 3 4

allnums： 4 3 3 2

因此需要在每一层对一种元素的个数进行枚举，为了便于枚举所有状态尤其空状态，使用下面的循环

1 backtrack(index): 2  3 　　...... 4  5 　　for k=1:allnums[index] 6  7 　　   add(alldigits[index]) 8  9 　　   backtrack(index+1)10 11 　　end for12 13 　　for k=1:allnums[index]14 15 　　   remove(alldigits[index])16 17 　　end for18 19 　　backtrack(index+1);

当然上面的对于空状态的遍历也可以放到非空状态之前，也就是

1 backtrack(index): 2  3 　　...... 4      backtrack(index+1); 5 　　for k=1:allnums[index] 6  7 　　   add(alldigits[index]) 8  9 　　   backtrack(index+1)10 11 　　end for12 13 　　for k=1:allnums[index]14 15 　　   remove(alldigits[index])16 17 　　end for

上面的遍历过程，在对index位的element处理完成之后，就需要将当前所添加的元素都要删除掉。不然在再次达到这个元素时会发生重复。

 

这样就可以遍历所有的状态

二、第一种思路的代价是需要提前知道每一种元素的个数。在【1】中的的思路可以省去这种计算。在每一层递归节点，所选择的元素不能重复，然后从被选择节点的下一个节点开始进行递归。

缺点：如果串比较长，可能会溢出

总结：已改还是第一个比较安全一些。

[1]

[2]