什么是回溯算法

本篇內(nèi)容介紹了“什么是回溯算法”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

• 1 <= nums.length <= 8

• -10 <= nums[i] <= 10

Analysis

回溯算法

與LeetCode - Medium - 46. Permutations類似，不同之處在于給定一個可包含重復(fù)數(shù)字的序列，要返回所有不重復(fù)的全排列，這里涉及到去重。

去重一定要對元素進(jìn)行排序，這樣我們才方便通過相鄰的節(jié)點來判斷是否重復(fù)使用。

以示例中的 [1,1,2]為例 （為了方便舉例，已經(jīng)排序）抽象為一棵樹，去重過程如圖：

圖中我們對同一樹層，前一位（也就是nums[i-1]）如果使用過，那么就進(jìn)行去重。

拓展

去重最為關(guān)鍵的代碼為：

if (used[i] || i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
	continue;

如果將!used[i - 1]改成 used[i - 1]， 結(jié)果也是正確的！很神奇。

if (used[i] || i > 0 && nums[i - 1] == nums[i] && used[i - 1])
	continue;

這是為什么呢，就是上面我剛說的，如果要對樹層中前一位去重，就用!used[i - 1]。如果要對樹枝前一位去重用used[i - 1]。

對于排列問題，樹層上去重和樹枝上去重，都是可以的，但是樹層上去重效率更高！

用[1,1] 來舉一個例子。

樹層上去重(!used[i - 1])，的樹形結(jié)構(gòu)如下：

樹枝上去重（used[i - 1]）的樹型結(jié)構(gòu)如下：

用[1,1,1] 再來舉一個例子。

樹層上去重(!used[i - 1])，的樹形結(jié)構(gòu)如下：

樹枝上去重（used[i - 1]）的樹型結(jié)構(gòu)如下： 顯然，樹層上對前一位去重非常徹底，效率很高，樹枝上對前一位去重雖然最后可以得到答案，但是做了很多無用搜索。

小結(jié)

樹層上去重要加上!used[i - 1]，似非而是，代碼結(jié)合圖加深理解吧！

參考

1. 回溯算法：排列問題（二）

Submission

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationsII {
	public List<list<integer>&gt; permuteUnique(int[] nums) {
		List<list<integer>&gt; result = new ArrayList&lt;&gt;();
		List<integer> path = new ArrayList&lt;&gt;();
		boolean[] used = new boolean[nums.length];
		Arrays.sort(nums);
		backtracking(path, nums, used, result);
		return result;
	}

	private void backtracking(List<integer> path, int[] nums, boolean[] used, List<list<integer>&gt; result) {
		if (path.size() == nums.length) {
			result.add(new ArrayList&lt;&gt;(path));
			return;
		}

		for (int i = 0; i &lt; nums.length; i++) {
			if (used[i] || i &gt; 0 &amp;&amp; nums[i - 1] == nums[i] &amp;&amp; !used[i - 1])
				continue;

			used[i] = true;
			path.add(nums[i]);
			backtracking(path, nums, used, result);
			path.remove(path.size() - 1);
			used[i] = false;
		}

	}

}

Test

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;

import org.hamcrest.Matcher;
import org.junit.Test;

@SuppressWarnings("unchecked")
public class PermutationsIITest {

	private final int[] array1 = {1, 1, 2};
	private final int[] array2 = {1, 2, 3};
	private final int[] array3 = {0, 1, 0, 0, 9};
	
	private final Matcher<iterable<? extends list<integer>&gt;&gt; expected1 = containsInAnyOrder(Arrays.asList(1,1,2), // 
			Arrays.asList(1,2,1), Arrays.asList(2,1,1));
	private final Matcher<iterable<? extends list<integer>&gt;&gt; expected2 = containsInAnyOrder(Arrays.asList(1,2,3), Arrays.asList(1,3,2),// 
			Arrays.asList(2,1,3), Arrays.asList(2,3,1), Arrays.asList(3,1,2), Arrays.asList(3, 2, 1));
	
	private final String expected3String = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,0,1],"//
									+ "[0,0,9,1,0],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,0,1],"//
									+ "[0,9,0,1,0],[0,9,1,0,0],[1,0,0,0,9],[1,0,0,9,0],[1,0,9,0,0],"//
									+ "[1,9,0,0,0],[9,0,0,0,1],[9,0,0,1,0],[9,0,1,0,0],[9,1,0,0,0]";
		
	private final Matcher<iterable<? extends list<integer>&gt;&gt; expected3 = containsInAnyOrder(string2IntegerList(expected3String));
	
	@Test
	public void test() {
		PermutationsII obj = new PermutationsII();

		assertThat(obj.permuteUnique(array1), expected1);
		assertThat(obj.permuteUnique(array2), expected2);
		assertThat(obj.permuteUnique(array3), expected3);
	}
	
	private List<integer>[] string2IntegerList(String original){
		List<integer>[] result;
		original = original.substring(1, original.length() - 1);
		String[] strs = original.split("\\],\\[");
		result = new ArrayList[strs.length];
		for(int i = 0; i &lt; strs.length; i++) {
			String[] nums = strs[i].split(",");
			List<integer> list = new ArrayList&lt;&gt;();
			for(String num : nums) {
				list.add(Integer.valueOf(num));
			}
			result[i] = list;
		}
		return result;
	}
	
	
	@Test
	public void testString2IntegerList() {
		String str = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,1,0],"
				+ "[0,0,9,0,1],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,1,0],"
				+ "[0,9,0,0,1],[0,9,1,0,0],[0,9,0,1,0],[0,9,0,0,1],[1,0,0,0,9],"
				+ "[1,0,0,9,0],[1,0,9,0,0],[1,9,0,0,0],[9,0,0,1,0],[9,0,0,0,1],"
				+ "[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1],[9,1,0,0,0],[9,0,0,1,0],"
				+ "[9,0,0,0,1],[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1]";
		System.out.println(string2IntegerList(str));
	}
	
}

“什么是回溯算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！