vector<vector<int>> fourSum(vector<int>& nums, int target) {
    set<vector<int>> ans;
    for (size_t i = 0; i < nums.size(); ++i) {
	for (size_t j=i+1; j < nums.size(); ++j) {
	    for (size_t k=j+1; k < nums.size(); ++k) {
		for (size_t m=k+1; m < nums.size(); ++m) {
		    if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
			vector<int> t({nums[i], nums[j], nums[k], nums[m]});
			sort(t.begin(), t.end());
			ans.insert(t);
		    }
		}
	    }
	}
    }
    return vector<vector<int>>(ans.begin(), ans.end());
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> ans;
    std::sort(nums.begin(), nums.end());
    for (size_t i = 0; i < nums.size();) {
	int n1 = nums[i];
	int target_1 = target - n1;
	for (size_t j=i+1; j<nums.size();) {
	    int n2 = nums[j];
	    int target_2 = target_1 - n2;

	    int front = j+1;
	    int end = nums.size() - 1;
	    while (front < end) {
		int n3 = nums[front];
		int sum = n3 + nums[end];
		if (sum == target_2) {
		    ans.push_back(vector<int> ({n1, n2, n3, nums[end]}));
		    do { ++front; } while(front < end && nums[front] == n3);
		}
		else if (sum > target_2) {
		    --end;
		}
		else {
		    ++front;
		}
	    }
	    do { ++j; } while (j<nums.size() && nums[j] == n2);
	}
	do { ++i; } while (i < nums.size() && nums[i] == n1);
    }
    return ans;
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> res;
    if (nums.size() < 4) return res;
    sort(nums.begin(), nums.end());
    int len = nums.size();
    for (int i = 0; i < len-3; i++) {
	//avoid duplicate
	if (i > 0 && nums[i] == nums[i-1]) continue;
	// if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
	// if (nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target) continue;
	//version3: less tight pruning
	if (4 * nums[i] > target) break;
	if (nums[i] +  3 * nums[len-1] < target) continue;
	for (int j = i+1; j < len-2; ++j) {
	    if (j > i+1 && nums[j] == nums[j-1]) continue;
	    // if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
	    // if (nums[i] + nums[j] + nums[len-2] + nums[len-1] < target) continue;
	    //version3: less tight pruning
	    if (nums[i] + 3* nums[j] > target) break;
	    if (nums[i] + nums[j] + 2 * nums[len-1] < target) continue;
	    //now the problems becomes 3 sum problem and only two other elements only to be considered
	    int left  = j+1, right = len-1;
	    int sofar = nums[i] + nums[j];
	    while (left < right) {
		if (sofar + nums[left] + nums[right] == target) {
		    res.push_back(vector<int>({nums[i], nums[j], nums[left], nums[right]}));
		    //how to skip the duplicate left and right
		    //version1: my own version
		    //  left++;
		    //  right--;
		    //  while (left < right && nums[left-1] == nums[left])  ++left;
		    // while (right > left && nums[right+1] == nums[right]) --right;
		    //version2: refer others
		    do{left++;} while (left < right && nums[left] == nums[left-1]);
		    do{right--;} while (right > left && nums[right] == nums[right+1]);
		}
		else if (sofar + nums[left] + nums[right] < target) left++;
		else right--;
	    }
	}
    }
    return res;
}

vector<string> letterCombinations(string digits) {
    vector<string> ans;
    if (digits.empty()) {
	return ans;
    }

    vector<string> letters {"",  "", "abc", "def", "ghi",
	    "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<int> carry(nums.size(), 0);
    vector<int> nums;
    for (char ch : digits) {
	int n = ch - '0';
	nums.push_back(n);
    }

    do{
	string str;
	for (size_t i=0; i<carry.size(); ++i) {
	    str += letters[nums[i]] [carry[i]];
	}
	ans.push_back(str);

	int c = 1;
	for (int i=carry.size()-1; i >= 0; --i) {
	    int d = carry[i] + c;
	    if (d >= letters[nums[i]].size()) {
		carry[i] = 0;
		c = 1;
	    }
	    else {
		carry[i] = d;
		c = 0;
		break;
	    }
	}

	if ( 1 == c) {
	    break;
	}

    } while (1);

    return ans;
}

class Solution {
    char mMap[8][4] = {
	{'a', 'b', 'c', '#'},
	{'d', 'e', 'f', '#'},
	{'g', 'h', 'i', '#'},
	{'j', 'k', 'l', '#'},
	{'m', 'n', 'o', '#'},
	{'p', 'q', 'r', 's'},
	{'t', 'u', 'v', '#'},
	{'w', 'x', 'y', 'z'},
    };

public:
    vector<string> letterCombinations(string digits) {
	vector<string> result;
	backTrack(digits, result, "", 0);
	return result;
    }

    void backTrack(string &digits, vector<string> &result, string combination, int index) {
	if (index >= digits.length()) {
	    if (combination.empty()) {
		return;
	    }
	    result.push_back(combination);
	    return;
	}
	for (char c : mMap[digits[index] - '2']) {
	    if (c == '#')
		continue;

	    combination += c;
	    backTrack(digits, result, combination, index+1);

	    // 这里为什么要删去最后一个呢？
	    // 因为之前在尾部追加了一个c
	    combination.erase(combination.end() - 1);
	}
    }
};

public List<String> letterCombinations(String digits) {
    LinkedList<String> ans = new LinkedList<String>();
    if(digits.isEmpty()) {
	return ans;
    }

    String[] mapping = new String[] {"0", "1", "abc", "def",
				     "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    ans.add("");
    for(int i=0; i<digits.length(); i++) {
	int x = Character.getNumericValue(digits.charAt(i));

	while(ans.peek().length() == i) {
	    String t = ans.remove(); // remove是从头部删去一个元素
	    for(char s : mapping[x].toCharArray()) {
		ans.add(t+s); // add是向尾部添加一个元素
	    }
	}
    }
    return ans;
}

public List<String> letterCombinations(String digits) {
    LinkedList<String> ans = new LinkedList<String>();
    if(digits.isEmpty()) {
	return ans;
    }
    String[] mapping = new String[] {"0", "1", "abc", "def",
				     "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    ans.add("");
    while(ans.peek().length() != digits.length()){
	String remove = ans.remove();
	String map = mapping[digits.charAt(remove.length())-'0'];
	for(char c: map.toCharArray()){
	    ans.addLast(remove+c);
	}
    }
    return ans;
}

int threeSumClosest(vector<int>& nums, int target) {
    if (nums.size() < 3) {
	return 0;
    }

    int ans = nums[0] + nums[1] + nums[2];
    int diff = abs(target - ans);

    // 穷举出所有的组合，与target比较，找到最接近的
    for (int i=0; i < nums.size(); ++i) {
	for (int j=i+1; j < nums.size(); ++j) {
	    for (int k=j+1; k < nums.size(); ++k) {
		int sum_t = nums[i] + nums[j] + nums[k];
		int diff_t = abs(target - sum_t);

		ans = diff_t < diff ? (diff = diff_t, sum_t) : ans;

		if (ans == target) {
		    return ans;
		}
	    }
	}
    }

    return ans;
}

int threeSumClosest(vector<int>& nums, int target) {
    if (nums.size() < 3) {
	return 0;
    }

    sort(nums.begin(), nums.end());

    int ans = nums[0] + nums[1] + nums[2];
    int diff = abs(target - ans);

    for (int i=0; i < nums.size(); ++i) {
	int n1 = nums[i];
	int front = i + 1;
	int end = nums.size() - 1;

	while (front < end) {
	    int n2 = nums[front];
	    int n3 = nums[end];
	    int sum = n1 + n2 + n3;
	    int diff_t = abs(target - sum);

	    if (diff > diff_t) {
		ans = sum;
		diff = diff_t;
	    }

	    if (sum == target) {
		return sum;
	    }
	    else if (sum > target) {
		--end;
	    }
	    else {
		++front;
	    }
	}
    }

    return ans;
}