排列组合-一一网

生成所有排列

方法1：依次取下标为0~n-1的数字到第一位，递归生成剩下的数字的排列。

方法2：
1)寻找以末尾元素结尾的降序序列。
2)假设降序序列为从n-i…n-1, 那么下一个排列为：从n-i到n-1中，找到比n-i-1大的最小的数n-p，交换n-i-1与n-p, 然后reverse(n-i, n-i-1,…n-1)
3)假设没有降序，只有升序，那么直接交换末尾两个元素。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var partition = (arr, start, end) => {
    let target = arr[start], i = start + 1, j = end;
    while(i <= j) {
       if (arr[i] > target) {
           let tmp = arr[j];
           arr[j] = arr[i];
           arr[i] = tmp;
           j--;
       } else {
           i++;
       }
    }

    arr[start] = arr[i - 1];
    arr[i - 1] = target;
    return i - 1;
};

var quicksort = (arr, start, end) => {
    if (start >= end) return;
    let pos = partition(arr, start, end);
    quicksort(arr, start, pos - 1);
    quicksort(arr, pos + 1, end);
};

var binarySearchPos = (nums, start, end, target) => {
    if (target < nums[end]) return end;
    while (start <= end) {
        let middle = Math.floor((start + end) / 2);
        if (target < nums[middle] && target > nums[middle + 1]) {
            return middle;
        } 
        if (target < nums[middle]){
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }
};

var swapArr = (nums, start, end) => {
    while(start < end) {
        let tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
        start++;
        end--;  
    }
};

var generateNextPermutation = (num) => {
   let i = num.length - 1;
   for (; i > 0; i--) {
       if (num[i - 1] < num[i]) {
           break;
       }
   }
   if (i == 0) {
       return null;
   } else {
       let pos = binarySearchPos(num, i, num.length - 1, num[i - 1]);
       let tmp = num[i-1];
       num[i - 1] = num[pos];
       num[pos] = tmp;
       swapArr(num, i, num.length - 1);
       return [...num];
   }
};

var permute = function(nums) {
    //依次生成下一个数。
    quicksort(nums, 0, nums.length - 1);
    let result = [[...nums]], next = generateNextPermutation(nums);
    while(next) {
        result.push(next);
        next = generateNextPermutation(nums);
    }
    return result;
};
复制代码

下一个排列(可能有相等数字)

题目：如题

解法：找到末尾降序序列i~n-1, 二分查找找出比i-1大的最小的数，交换。剩下的数reverse.

复制代码

m * n矩阵从左上到右下走法

解法：C(m+n, n);

tip:
C(n, m) = n! /( m! * (n-m)!)
A(n, m) = n! / m!

求1~n的k个元素组合

解法：初始值为1k顺排，加哨兵元素n+1
每次用当前组合迭代出下一个，迭代方法为找出迭代位，顺排序列，固定序列。
迭代位：后面的数比它大不止1
顺排位:前面1i-1个数即是1~i-1
固定位：后面[i+1, k]个数不会改变，已排好，并且是[k-i+1, k]。

比如n=5, k=4, 序列[1, 2, 4, 5, 6], 哨兵为6， 迭代位是2， 顺排序列为[1], 固定序列为[4, 5].
复制代码

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    var temp = [], ans = [];
    
    for (var i = 1; i <= k; i++) {
        temp.push(i);
    }
    temp.push(n+1);
    
    let j = 0;
    ans.push(temp.slice(0, k));
    while(j < k) {
        while(temp[j] + 1 == temp[j + 1]) j++;
        temp[j]++;
        if (j >= k) break;
        while(j >= 1) {
            temp[--j] = j + 1;
        }
        ans.push(temp.slice(0, k));
    }
    return ans;
};
复制代码

5、求数组中和为target的所有子序列

解法：回溯，不断选择当前数字是否放入

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    var ans = [];

    var map = {}, freq = [], nums = [];
    candidates.forEach(num => {
        map[num] = (map[num] || 0) + 1;
    });

    for (var num in map) {
        if (map.hasOwnProperty(num)) {
            nums.push(Number(num));
            freq.push(map[num]);
        }
    }
    
    var bag = function(rest, combine, numIdx, curFreq) {
        if (rest == 0) {
            ans.push(combine);
            return;
        }
        if (numIdx == nums.length) {
            return;
        }
        
        if (rest - nums[numIdx] >= 0 && curFreq <= freq[numIdx]) {
            bag(rest - nums[numIdx], [...combine,  nums[numIdx]], numIdx, curFreq + 1);
        }
        bag (rest, combine, numIdx + 1, 1);
    }

    bag(target, [], 0, 1);
    return ans;
};
复制代码