감소하지 않는 시퀀스

요구 사항: 정수의 배열이 주어졌을 때, 원소가 2개 이상인 배열의 모든 고유한 증가 수열을 찾아서 반환합니다. 어떤 순서로든 답을 반환할 수 있습니다.

배열에는 두 개의 정수가 동일한 경우와 같이 중복 요소가 포함될 수 있으며, 이는 증분 시퀀스의 특수한 경우로 간주할 수도 있습니다.

아이디어

1. 종료 조건: 문제에 증분 시퀀스에 최소 두 개의 요소가 필요하므로 경로.길이 > 1

2.이 질문의 어려움은 정렬과 함께 디 엠 퍼시스를 수행하는 방법과 사용 된 디 엠 퍼시스가 다르며,이 질문은 아래 그림에서 볼 수 있듯이 먼저 정렬 할 수 없으며 사용 된 요소의 동일한 계층 아래에있는 동일한 상위 노드를 다시 사용할 수 없으며 동일한 수준의 디 엠 퍼시스를 사용하여 SET를 수행 할 수 있으며 단일 레벨 검색의 증분 후속인지 확인하여 각 획득 요소가 경로에서 마지막보다 경로의 값보다 마지막에 획득한 요소가 있는지 확인해야 합니다.

var findSubsequences = function(nums) {
 let res = [], path = []
 function backstracking(nums, startIndex){
 if(path.length >1){
 res.push([...path])
 }
 let set = new Set() //이 레이어를 중복 제거하려면 set를 사용합니다.
 for(let i=startIndex; i<nums.length; i++){
 if(path.length != 0 && nums[i] < path[path.length-1] 
 || set.has(nums[i])){
 continue
 }
 set.add(nums[i])
 path.push(nums[i])
 backstracking(nums, i+1)
 path.pop()
 }
 }
 backstracking(nums, 0)
 return res
};

전체 배열

Link

요구 사항: 반복되는 숫자가 없는 배열의 숫자가 주어지면 이를 반환합니다. 어떤 순서로든 답을 반환할 수 있습니다.

아이디어

이 질문은 배열이기 때문에 for 루프는 startIndex 시작이 아니라 0부터 시작하지만, 이때 사용된 레코드는 어떤 요소가 사용되는 경로에서 사용해야 하며, 요소의 배열은 한 번만 사용할 수 있습니다.

var permute = function(nums) {
 let res = [], path = []
 let used = new Array(nums.length).fill(0)
 function backstracking(nums){
 if(path.length == nums.length){
 res.push([...path])
 return 
 }
 for(let i=0; i<nums.length; i++){
 if(used[i] == 1) continue
 used[i] = 1
 path.push(nums[i])
 backstracking(nums)
 path.pop()
 used[i] = 0
 }
 }
 backstracking(nums)
 return res 
};

요구 사항: 반복되는 숫자를 포함할 수 있는 시퀀스 숫자가 주어지면 반복되지 않는 모든 숫자의 전체 순열을 반환합니다.

아이디어

이 질문은 중복된 숫자가 존재하기 때문에 트리 수준의 중복 제거가 필요한지, i>0 && nums[i] == nums[i-1] && used[i-1] == 0 여기서 사용[i-1] == 0은 트리 수준에서 중복 제거를 의미하고, 사용[i-1] == 1이면 트리 가지의 중복 제거를 수행하며, 여기서 트리 가지 중복 제거도 전달할 수 있지만 효율성은 상대적으로 낮습니다.

var permuteUnique = function(nums) {
 nums.sort()
 let res = [], path = []
 let used = new Array(nums.length).fill(0)
 function backstracking(nums){
 if(path.length == nums.length){
 res.push([...path])
 return 
 }
 for(let i=0; i<nums.length; i++){
 if(i>0 && nums[i] == nums[i-1] && used[i-1] == 0){ //트리 레벨 중복 제거
 continue 
 }
 if(used[i] == 0){ //이전 번호를 제거하기 위해 관계의 배열이 선택되었습니다.
 path.push(nums[i])
 used[i] = 1
 backstracking(nums)
 used[i] = 0
 path.pop()
 }
 }
 }
 backstracking(nums)
 return res
};